On Tue, Feb 25, 2014 at 9:53 PM, Ben Goertzel <[email protected]> wrote:
> 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 > "Number of Turing machines of size N that execute in polynomial time" seems to be an incomputable number -- due to the halting problem... no? 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 > 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). > There may exist just a small number of Turing machines that can solve an NP-hard problem in polynomial time, with the problem-size N as an input parameter. That would allow P=NP without violating your counting argument.... Good algorithms are hard to find, but when they do exist, they prove that it is possible =) ------------------------------------------- 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
