and then there is the constant of relative visual perception of general reality?
> Date: Thu, 5 Mar 2015 22:01:21 -0500 > Subject: Re: [agi] SAT and Dynamic Programs of Models > From: [email protected] > To: [email protected] > > Matt said: > 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. > ------------------------------------------------- > This is a truly insipid response. You have taken one narrow situation > and used it in an over-generalization of a kind of AGI problem. "The > problem scales polynomially with input size? The point that I made is > that the general analysis of imagery is presumably as bad or worse > than NP (in the lexicon of the day). What I mean is that there is > sufficient evidence that AGI is, in the worse case, at least > exponentially difficult and that makes it worthwhile to examine why > that may be. One reason, the reason I gave, is that the easiest > methods to make a methodical and thorough analysis of the relations > between associated pixels would be those that are (literally) in NP. > The implied case of scaling a particular picture and arguing that it > would scale polynomially with input size is analogous to saying that > converting an unrestricted Boolean Satisfiability problem to 3-SAT > scales polynomially (and that somehow proves that unrestricted SAT > scales polynomially). It is pretty obvious that you have little > experience with visual data. > > This is an example of a blatant overgeneralization being declared as > if it were a factual statement. I can't casually explain why visual > analysis is at least exponentially difficult because I am not enough > of an expert to be that familiar with all the problems. However, I am > confident that there is no overwhelming evidence to suggest that, in > general, it is less difficult. > 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/26941503-0abb15dc > 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
