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/21088071-f452e424 Modify Your Subscription: https://www.listbox.com/member/?member_id=21088071&id_secret=21088071-58d57657 Powered by Listbox: http://www.listbox.com
