From: Gwern Branwen (gwern0@gmail.com)
Date: Tue Oct 20 2009 - 21:27:25 MDT
On Tue, Oct 20, 2009 at 10:13 PM, Matt Mahoney <matmahoney@yahoo.com> wrote:
> Pavitra wrote:
>> Just to check: I think you mean "...even if it turns out that P = NP"?
>
> No, I mean P != NP. Suppose it were proven. You would know that some instances of, say, SAT or traveling salesman required exponential time to solve, but you wouldn't know which ones. There are heuristics that can solve lot of NP-complete problems quickly, just not all of them. You don't know that any particular instance is hard because there might be another heuristic that makes it easy.
Couldn't we just ask our oracle NP the answers to all NP problems of
depth n? A heuristic by definition wouldn't work on all of them, and
it'd be cheap for us to check the answers are right.
Alternately, couldn't we just generate random examples until we're
satisfied? Our confidence would be no worse than that for
zero-knowledge proofs or hashes, for example.
-- gwern
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:01:05 MDT