The P=?NP Poll (2002) [pdf]
cs.umd.edu
cs.umd.edu
An oracle is a black box that can solve a particular decision problem in O(1).
The notation means e.g. P^SAT = class of all problems that can be solved in P time with a machine that has an oracle for SAT.
It gets really ingesting because there are particular oracle machines for which P^X == NP^X.
See https://en.m.wikipedia.org/wiki/Oracle_machine for references to papers.
Also see https://en.m.wikipedia.org/wiki/Almost_surely if you don't know what with probability 1 is.
Off topic (but related to almost surely), one of my favourite theorems is Pólya's recurrence theorem which says that a simple random walk on Z^d (lattice) is recurrent for d=1,2 and transient otherwise, so if you get lost on a 1 or 2 dimensional grid, just execute a simple random walk and you'll get back to the origin almost surely! IIRC the probability of recurrence is about 34% in 3d.
Wait, this has to be conditional on something. If P = NP, then P^X = NP^X for any oracle X, right? (It's been a while since my theoretical CS class, so maybe it's my naïve assumption that's not true.)
Edit: No, I think. See child comment by JadeNB.
Probably wrong { Yes, since we could just not invoke the oracle. But people do this sort of stuff to study it backwards e.g. what do P^X and NP^X (and any class^X) tell us about P and NP (and any other class). }
I hope this is clearer, let {A, B, C, ...} be the set of all oracles.
For TM + A:
P^A is the class of problems that can be done in P time on this machine.
NP^A is the class of problems that can be done in NP time on this machine.
Similarly for
TM + B
TM + C ...
This theorem says that if we choose one of these oracle machines uniformly at random then P =/= NP in _its_ model of computation a.s.
This is an entirely probabilistic statement about machines that are more "powerful" than standard TMs.
I think that only shows that P^X contains P and NP^X contains NP, not that P = NP implies P^X = NP^X. Indeed, my supposition that this implication holds seems to be false; openasocket (https://news.ycombinator.com/item?id=12893077) points to a paper mentioning a specific example of an oracle B so that P^B \ne NP^B. If my naïve reasoning were correct, then we'd be able to deduce that P \ne NP; but we famously can't.
P and NP are not the machine, but the set of problems solvable by deterministic/non-deterministic Turing machines limited to a polynomial number of steps. P^X is set of problems solvable by a deterministic Turing machine with access to oracle X, which is fairly straight forward, but need have little to with P. Similarly, NP^X is the set of problems solvable by a non-deterministic Turing machine with access to oracle X. However, this means if there's any input it could ask X to get an answer it can use to solve the problem, it can solve the problem, which may be vastly more efficient than trying to construct the right question to ask.
Essentially it boils down to: Just because two different models of computation can solve the same problems, does not mean that when augmented by the same oracle can solve the same problems (they can access the oracles in different ways).
Indeed, it was just the worry that something nasty like this could happen that made me weasel my initial definite assertion into the form of a question. Thank you for this informal explanation; it nicely complements openasocket's formal reference (https://news.ycombinator.com/item?id=12893077).
(Long-delayed post because "You are submitting too fast".)
No, surprisingly, it's not true!
The problem is that a nondeterministic turing machine can ask "more" or "better" questions of an oracle than a deterministic one. Intuitively, it can ask an exponential number of questions and then accept if any of the answers turn out to be "useful".
So even if we know they solve the same problems when unaided by an oracle, this doesn't imply that an oracle amplifies their abilities in the same way.
Here's a short-ish overview: http://www.math.uchicago.edu/~may/VIGRE/VIGRE2011/REUPapers/...
For a more extensive overview, try this textbook by Michael Sipser (Amazon Affiliate Link if feeling generous: http://amzn.to/2fy9tKZ, Google Books link otherwise: https://books.google.com/books?id=1aMKAAAAQBAJ&dq=introducti...).
Edit: to be honest it's the maths notation that is a big barrier for me. Until one can read it relatively fluently it's very hard to translate the ideas into a meaningful mental model .
Seems like a few lectures are missing but if you google around you might be able to find them somewhere.
I later on picked up the first two editions of Hopcroft & Ullman for $1 each at a used book store. I don't think either edition can really hold a candle to the Sipser book, which is shorter, more thorough, and (imo) easier to understand.
One caveat: it's super-expensive. I'd recommend finding a used copy or even an "international edition" (which will be soft-cover rather than hard-cover, but the content is the same).
The rest of computational theory will follow.
Essentially, "does being able to quickly recognize correct answers mean there's also a quick way to find them?"
Not all that in-depth, but it's a great starting point.
In other words, let the characteristic sequence of the language be an infinite random binary string.
"Proof by contradiction. Assume P = NP. Let y be a proof that P = NP. The proof y can be verified in polynomial time by a competent computer scientist, the existence of which we assert. However, since P = NP, the proof y can be generated in polynomial time by such computer scientists. Since this generation has not yet occurred (despite attempts by such computer scientists to produce a proof), we have a contradiction."
THEOREMS (the language of correct proofs) is in P; given a correct proof (possibly restricted to being in first-order logic), it can be verified in polynomial time. In the first-order logic case, all you have to do is read the proof from beginning to end and verify that each statement follows from either an axiom or an already-established statement. This is done entirely syntactically, requiring no knowledge of the underlying mathematics.
However, to do this requires formalizing the entire proof in machine-checkable format, which is a substantial undertaking even for relatively simple proofs and will likely take far longer than polynomial time.
An interesting and still valid point, however, is that P=NP may be undecidable (in the sense of Gödel's incompleteness theorem). In other words, our current axioms may be insufficient to prove or disprove P=NP.
http://www.scottaaronson.com/papers/pnp.pdf
> P != NP is either true or false. It’s one or the other. But we may not be able to prove which way it goes, and we may not be able to prove that we can’t prove it.
That seems to be an argument for the uselessness of the distinction between P-with-large-exponent and not-P, not for the uselessness of having a reduction of NP to P.
Also, it's worth noting that, if one is a theoretical computer scientist, then there is more of interest in the study of computing than what can be done in the universe. (I am a mathematician, and am, as I suspect most of my colleagues, serenely unconcerned with the applicability or non- of my work.)
And the parent is pointing out that if P=NP, we already have a construction.
So (if his opinion was presented accurately), Knuth is wrong about a positive proof being non-constructive.
---
I believe there are already known problems whose best solution is O(n^k) for arbitrarily high k. So yeah, naturally not everything will be practically tractable.
A good argument can be provided by an analysis of statistical thermodynamics gas laws. It highly disturbs some people to think that atoms being in motion implies that all the oxygen atoms in the room air might coincidentally cluster into a small corner of the room leaving the victim to suffocate. There is no reason to think that impossible under most thermodynamics theories. However, it is nearly infinitely unlikely and you'd merely have to wait a ten to the hundred times the lifespan of the universe for it to coincidentally happen. I suppose it scales quite strongly with room volume and linearly with air pressure, you have one atom in the ISS airlock and being in one half the air lock at any given moment is a very predictable 50:50 odds...
Likewise if the smallest polynomial solution to a NP problem takes a google's worth of universes to calculate, then even if it is poly you need not worry too much about mere human inconvenience.
I'm not saying its a wise way to go thru life, but there exists a large set of people who get hung up on whats convenient or beautiful must be right, even if whats right turns out to be very ugly or inconvenient, so for them "P=NP but your bank account is still secure" is a very big deal.
That said, this algorithm does not solve the decision problem because it can never return a no. Only a yes if there is one to be found.
Donald Knuth: (Retired from Stanford) It will be solved by either 2048 or 4096. I am currently somewhat pessimistic > by either 2048 or 4096
Because of some hand wavy string theory calculation completed in 2030, either the universe doesn't exist as it is measured to exist (or whatever McGuffin you'd like as a bullet proof excuse) or there exists a Turing machine that outputs a proof of P=NP then halts and the fastest way to find out if it halts is to run it and we try and it never stops. Maybe a century later someone figures out a lower bound on the number of steps the machine will make before it halts and its larger than the computational power of the lifetime of the universe, even very optimistically. Or a ruleset is proven to exist but the ruleset is at minimum a number larger than the number of particles in the universe so its kinda difficult to construct or emulate. Or the infinitely long Turing tape is merely proven to contain a number of states equal to a trillion times the number of atoms in the universe.
For instance, a decade before Wiles' proof of Fermat's Last Theorem, Feynman[1] showed it was extremely unlikely to be false. While you're not getting a million from Clay for that, it something non insignificant that we can use to guide our intuition.
[1]http://www.lbatalha.com/blog/feynman-on-fermats-last-theorem
http://epubs.siam.org/doi/abs/10.1137/0210008
Edit: For those who are interested, the oracle separation gives you one of the few properties we can prove about the nature of any proof of P ?= NP, that it must be 'non-relativizing'. We know a few other properties of any possible proof, described here: http://www.scottaaronson.com/papers/alg.pdf
I believe that the traditional proof techniques will not suffice. Something entirely novel will be required.
My hunch is that the problem will be solved by a young researcher who is not encumbered by too much conventional wisdom about how to attack the problem.
Actually, there has been tremendous incremental progress in inventing better and better algorithms for NP Complete problems. As a result, these problems are more deeply understood now. I think that the gap to poly time is closing fast.
Contrast that with the almost complete absence of progress in proving P != NP.
Also, from a practical viewpoint, many NP Complete problems of industrial size are now solved routinely.
Seriously, if you're interested in this approach ("well, in practice we can solve the problem if [insert thing here] is bounded"), check out the field of parameterized complexity. It's very popular in the database area. It also reveals some very sharp limits to tractability for these problems in practice, not just in theory.
I probably don't understand the proofs of these bounds - it seems to me though, that any lower bound without some relationship to the time or space to input the problem into some kind of computer, implies a belief that an instance might be solvable in-place, in some physical system.
I have some doubts about that ....
To more specifically address your "in-place" concerns, you can often formulate the problem in terms of circuit complexity--circuits are inherently parallel, so minimum circuit depth is a good proxy for a required number of steps, and it's also generally agreed that if you can design a circuit to do something it's physically realizable (even though that's arguably not always true, especially in cases with very wide fanout). So a (somewhat) promising direction has been to try to find circuit complexity lower bounds for problems, especially nontrivial ones.
We've ruled out a number of techniques and also have shown that any solution must fall into a category avoiding a number of conditions (natural proof, algebrization barrier). Note also Ryan Williams' result separating ACC0 and NEXP. All of that is progress as I see it.
It's simply that construction of practical approximation algorithms or heuristics that work on large instance is (in general) much easier than separating proofs for complexity classes.
I agree, but the search for better algorithms is also more principled. At some point, separating complexity classes looks like counting the number of angels on a pinhead. It's probably interesting in an abstract way for some people - but it's not my cup of tea, as they say.
> As a result, these problems are more deeply understood now. I think that the gap to poly time is closing fast.
I'd disagree. As we develop more and more understanding of these problems, we still are only improving exponentials to other exponentials (in theory - practice may be different) and so we remain in a fundamental sense as far away from polynomial-time solutions as ever, despite improved understanding.
For example in SAT, the distance of the instance to the critical clause/variable threshold. In subset sum, the density of the instance.
It's not the problem class that matters.
"Stuart Kurtz (University of Chicago, 2050, P!=NP) [on wether and when proof will be found]:
Knowing Ketan Mulmuley, I live in fear that the solution will be via algebraic geometry, and it will come soon enough that I’ll be expected to understand it. An alternative nightmare is that the undergraduate who solves it will publish his solution in French."
But it is by far not the only funny opinion in this paper.
> My longest-surviving proof that NP does not equal co-NP (about 5 years ago) survived for about 3 days and fooled some very smart people into believing it.
Is this a path towards selecting by insidiousness of mistakes? Can we mistakenly prove something by evolving a method by which no-one can figure out what is wrong with it.
Is there a limit to how hard it is to identify a mistake in a false proof? If incompleteness keeps you up at night, how about the possibility of a proof that you can have a mistaken proof in which the mistake was provably unidentifiable.
From a sociological perspective, since most mathematicians don't use formal methods for most of their proofs, there can of course be proofs that may be right, but that nobody can understand well enough to verify. The ongoing famous example here is that of Shinichi Mochizuki: http://www.nature.com/news/the-biggest-mystery-in-mathematic....
Anyway, neither of these seem too relevant to P vs. NP.