From: Matt Mahoney (matmahoney@yahoo.com)
Date: Wed Oct 21 2009 - 09:50:43 MDT
Gwern Branwen wrote:
> 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.
No, because there are 2^n answers to check. P != NP only tells you that at least one of them requires exponential time to solve.
> 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.
No, because you don't know what fraction of the problems are hard to solve. Zero knowledge proofs assume that all (or some known fraction) of the problems are hard.
-- Matt Mahoney, matmahoney@yahoo.com
----- Original Message ----
From: Gwern Branwen <gwern0@gmail.com>
To: sl4@sl4.org
Sent: Tue, October 20, 2009 11:27:25 PM
Subject: Re: [sl4] to-do list for strong, nice AI
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