I strongly suspect that P != NP, and that the brain makes it look as though P = NP by taking full advantage of the probability distribution of the problem space and optimizing towards the most commonly encountered types. Applying the 80/20 rule, so to speak.
There is also the fact that, to my knowledge, no one has ever actually measured the solution times for humans solving NP hard problems. It may be that we simply don't notice how much longer we take on harder problems, or that there is such a large constant- or linear-time component that the exponential-time component is invisible at the scale of the problems that we tend to solve manually. On Tue, Feb 25, 2014 at 7:53 AM, Ben Goertzel <[email protected]> wrote: > Hmmm... P=NP is something that every hyperambitious geek who's studied > computer science has mused about, and all of our intuitions are probably > worth nil... > > But having said that, I'll share one of my many thoughts on the subject ;) > ... > > Intuitively, I suspect that P!=NP will eventually be demonstrated by some > sort of counting argument... > > That is, I suspect that if > > X = the number of polynomial-time algorithms > > Y = the number of problems in NP (i.e. for which potential solutions can > be checked in polynomial time) > > one can show somehow that > > X < Y > > and hence that P can't equal NP. > > It would have to be a carefully managed limiting argument; since in full > generality, of course, both of those classes are infinite.... That is, one > would have to talk about, given an appropriate Turing-complete language L, > > X = the number of distinct polynomial time algorithms describable in N > bits, in language L > > Y = the number of distinct problems for which there is a solution > describable in N bits in language L, for which potential solutions can be > checked in polynomial times > > (where it's assumed that each "algorithm" can solve exactly one problem, > in the presupposed formalism). > > This would follow if, basically: Out of all the programs of length N bits > or less, in language L, a lot more of these represent > {exponential-time-or-greater algorithms for problems with solutions > checkable in polynomial time} than polynomial-time algorithms. > > This sort of proof would bypass the theory of NP-completeness and so > forth, hence would be kinda eccentric with regards to standard theoretical > computer science... > > Part of the intuition here is that, for any general language and for > reasonably large N, most programs are going to have exponential or greater > runtime. This could be shown pretty easily I guess. The hard part would > be to show that, even if one restricts programs to have solutions checkable > in polynomial time, the majority of programs still have exponential or > greater runtime... > > Just some speculation ;p ... > > -- Ben > > > > > On Tue, Feb 25, 2014 at 6:28 PM, YKY (Yan King Yin, 甄景贤) < > [email protected]> wrote: > >> >> Yes, the r- result is for worst case (the approx algo has to guarantee a >> result that is r times the optimal, in all cases). That's why I say this >> particular definition of approx may not be a very good one. >> >> But what if similar results hold for other criteria of approximation? >> Then "P=NP approximately" would imply "P=NP exactly". >> >> A better definition of approx might require to distribute probabilities >> over all instances of an NP-hard problem, say SAT. That space may be >> infinite but countable -- I'll check. Since the P=?NP question is >> equivalent to the SAT ∈? P question, we only need to consider SAT. >> >> My intuition is this: if we have an algo that can approx NP good enough >> for many *general* cases, then why would it become impossible to approx NP >> for *all* cases? >> >> And if we can approx NP in polynomial time for all cases, then it should >> be that P = NP. >> *AGI* | Archives <https://www.listbox.com/member/archive/303/=now> >> <https://www.listbox.com/member/archive/rss/303/212726-deec6279> | >> Modify<https://www.listbox.com/member/?&;>Your Subscription >> <http://www.listbox.com> >> > > > > -- > Ben Goertzel, PhD > http://goertzel.org > > "In an insane world, the sane man must appear to be insane". -- Capt. > James T. Kirk > *AGI* | Archives <https://www.listbox.com/member/archive/303/=now> > <https://www.listbox.com/member/archive/rss/303/23050605-2da819ff> | > Modify<https://www.listbox.com/member/?&;>Your Subscription > <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
