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