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 On Fri, Mar 6, 2015 at 3:52 PM, Jim Bromer <[email protected]> wrote: > One other thing Matt. We have talked about this before. Your interest > in compression should tell you intuitively that the P<>NP theory is > unlikely. Are there any other compression schemes - that use systems > of algorithms but don't use special non-general individual > substitutions - that are exponentially efficient (for the strings that > they compress) and which are not reducible to Bool SAT? > > I would very interested in learning something about how something like > that works. > Jim Bromer > > > On Thu, Mar 5, 2015 at 1:04 PM, Matt Mahoney via AGI <[email protected]> wrote: >> On Wed, Mar 4, 2015 at 2:51 AM, Jim Bromer <[email protected]> wrote: >>> On Tue, Feb 17, 2015 at 11:52 PM, Matt Mahoney via AGI <[email protected]> >>> wrote: >>>> On Tue, Feb 17, 2015 at 10:26 PM, Jim Bromer via AGI <[email protected]> >>>> wrote: >>>>> I started wondering about how a good Satisfiability model might be >>>>> used with AGI. >>>> >>>> It wouldn't because the hard problems in AI like vision and language >>>> are not NP-hard. The more useful application would be breaking nearly >>>> all forms of cryptography. (One time pad would still be secure). >>>> -- Matt Mahoney >>> >>> I seriously doubt the premise that the hard problems like vision and >>> language in AI are not NP-hard. >> >> NP-hard means NP-complete or harder. NP-complete means that a solution >> would solve any problem in NP. NP is the class of problems whose >> answers can be verified in time that is a polynomial function of the >> input size. P is the class of problems that can be solved in >> polynomial time. It is widely believed by everyone except Jim Bromer >> that P != NP. This belief is not because of any proof, but because >> thousands of other people like Jim Bromer who believed P = NP failed >> to find polynomial time solutions to any NP-complete problems after >> years of effort until they were convinced they would be better off if >> they gave up. The time it takes to give up is inversely proportional >> to the person's efforts into studying the math and researching the >> work of others instead of repeating their mistakes. >> >>> My (admittedly limited) experience >>> with visual AI ran up against NP-Hard solutions that I thought would >>> work. >> >> Vision is a pattern recognition problem. You input a picture of a cat >> and output a label like "cat". It is not NP-complete because (1) >> experimentally, the problem scales polynomially with input size and >> (2) the time to verify that a label like "cat" is correct is about the >> same as the time it takes to label the image. Thus, the problem is in >> P and would not benefit even if P = NP. >> >>> And since language could be considered to be a form of >>> cryptography then your conjunction of cases (not language but >>> cryptography) does not look really strong. >> >> No, language is also a pattern recognition problem. >> >>> (Visual processing also >>> might be considered to be a form of cryptography and indeed it is used >>> as such in captchas.) >> >> Cryptography depends on the existence of one-way functions: given >> function f and output f(x), you can't find input x any faster than >> trying all possible values and comparing the outputs. If P = NP, then >> one-way functions would not exist. You could build a circuit that >> computes f and compares the output. Then set the bits of x one at a >> time and ask your polynomial SAT solver if a solution exists. If not, >> flip the bit before going to the next bit. >> >> You could argue that a captcha is a one way function. It is easy to >> convert text to an image, but hard to convert it back. But it is >> polynomially hard, not exponentially hard. Adding one bit to the image >> doesn't double the solution time, like adding one bit to an encryption >> key would. >> >> -- >> -- 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
