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
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
