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
