Well, just to finish my thought. The question now is whether I (or anyone else) could think of a way to compress multiple strings together so that: 1. The compression ration would be nearly logarithmic. 2. A decompression algorithm would be nearly exponential. 3. Any individual string in the set could be verified in fast polynomial time.
What kind of characteristics would this compression need? As I think of it, there are a number of additional conditions that need to be formed because the length an individual (average) string has to have a ratio to the number of strings that could be compressed. Jim Bromer On Fri, Mar 6, 2015 at 8:46 PM, Matt Mahoney via AGI <[email protected]> wrote: > On Fri, Mar 6, 2015 at 4:12 PM, Jim Bromer via AGI <[email protected]> wrote: >> Let me restate that question. >> Are there any other compression methods that have an average >> logarithmic compression ratio, which can take an exponential time to >> decompress using a general set of algorithms, that do not rely on any >> non-general special substitutions, which are not reducible to Boolean >> SAT and which *any* solution can be tested in polynomial time? >> >> I don't think that you will find a good reason to assume that P<>NP. >> Jim Bromer > > In general, optimal compression implies knowing the Kolmogorov > complexity, which is not computable. > > There are probably some contrived examples where P = NP would speed up > compression. Encrypted data cannot be compressed without knowing the > key. If P = NP, then the encryption would be broken and the data could > be compressed by first decrypting it. > > If a source has a logarithmic compression ratio, then decompression is > exponential but not in NP. For example, a string of n zero bits can be > compressed to just the number n, which has log(n) bits. Even if P = > NP, it still requires n operations to write the output. > > Anyway, my reason for believing P != NP is that cryptography still works. > > -- > -- Matt Mahoney, [email protected] > > > ------------------------------------------- > AGI > Archives: https://www.listbox.com/member/archive/303/=now > RSS Feed: https://www.listbox.com/member/archive/rss/303/24379807-653794b5 > Modify Your Subscription: https://www.listbox.com/member/?&; > Powered by Listbox: http://www.listbox.com ------------------------------------------- AGI Archives: https://www.listbox.com/member/archive/303/=now RSS Feed: https://www.listbox.com/member/archive/rss/303/21088071-f452e424 Modify Your Subscription: https://www.listbox.com/member/?member_id=21088071&id_secret=21088071-58d57657 Powered by Listbox: http://www.listbox.com
