A really cool result which seems relatively unknown is that if we augment our Turing machines with an oracle X chosen uniformly at random from all oracles then P^X =/= NP^X with probability 1.
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.
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.
This result is slightly less interesting that it sounds. "an oracle X chosen uniformly at random from all oracles" is also called a "random oracle", more commonly referred to nowadays as a cryptographically secure pseudo-random number generator. So what this is really saying is that "an oracle X chosen uniformly at random from all oracles" is almost certain to not do anything more interesting than produce numbers that indistinguishable from random, and hence cannot be compressed. So yes, it's a cool result, but not quite as earth-shattering as it may appear to be at first glance.
The Sipser book is excellent. It's one of only a handful of textbooks I decided to keep after I graduated from university. And perhaps the only one I kept because of how good it was rather than because the campus bookstore wanted to give me a pittance for it... and I didn't even buy the book until after the semester when I had to return the copy I'd checked out from the library...
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).
I bought Sipser for this very purpose. I found it very difficult without being able to discuss it with anyone to clarify my understanding of the ideas. I would love to work through it, but would need a CS tutor to help me... any takers? ;)
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 .
"Meta Math!: The Quest for Omega" by Gregory Chaitin [0] was my introduction to the theory of computability [1]. I found it enjoyable and approachable.
This 10 minute video is a great introduction to the P = NP problem and computational complexity theory if you have no context. I've shown this to plenty of friends (including those outside of computer science).
Essentially, "does being able to quickly recognize correct answers mean there's also a quick way to find them?"
What does it mean to take a random oracle from all oracles? How do you enumerate oracle-space? Is that something like the space of all problems, where each problem corresponds to an oracle for that problem?
Another way to enumerate oracles is to consider the set of terminating Turing machines (and enumerating them is itself uncomputable but whatever). Each TM corresponds to an oracle that computes its result in O(1).
> A really cool result which seems relatively unknown is that if we augment our Turing machines with an oracle X chosen uniformly at random from all oracles then P^X =/= NP^X with probability 1.
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.)
> If P = NP, then P^X = NP^X for any oracle X, right?
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.
It's tricky and the notation confuses things a bit.
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).
> 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".)
Thanks for that reference! I am glad that, even if my intuition led me astray, at least I had the foresight to append the weasel "… right?" to the end of my false claim. :-)
> If P = NP, then P^X = NP^X for any oracle X, right?
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.
#8 is a fun one (some of these answers are half-joking):
"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."
As petters points out, "X time" has no useful meaning here.
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.
> 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.
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.
Knuth's perspective on this topic is quite interesting, bordering on the infuriatingly frustrating: he seems to be of the opinion that p=np, but any proof we find for that will be non-constructive and the actual algorithm will evade us.
Fascinating. In fact by devoting half of its time to the first algorithm, a quarter to the second, and so on, it will solve it in the same big-O as the most efficient algorithm! (Albeit with a horrible constant.)
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.
This argument is useless since polynomial time is just as intractable as exponential time if the exponent is large. For example, lets say that we found a way to solve all np problems in n^1000 time, would that change anything? No, there aren't even 2^1000 atoms in the universe so we will only be able to solve it for the case n=1.
It might be useless for solving NP problems, but that's not the "point" of P=NP per say. P=NP is an intrinsically interesting math problem.
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.
> This argument is useless since polynomial time is just as intractable as exponential time if the exponent is large. For example, lets say that we found a way to solve all np problems in n^1000 time, would that change anything? No, there aren't even 2^1000 atoms in the universe so we will only be able to solve it for the case n=1.
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.)
Often a "proof" that P does not equal NP is that it would be terribly inconvenient if solvable in n to the second or whatever, and therefore in a sort of cosmic censorship saves us by claiming it clearly can't be the case because it would be so annoying.
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 is one interesting way to interpret the famous Aaronson soap bubble experimental results, and Yuri Gurevich's opinion is just a somewhat more optimistic version of it.
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.
Is there any probabilistic argument around the proof?
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.
As mentioned elsewhere in the thread, if provided with a random oracle A, P^A != NP^A with probability 1. It's not clear though what this actually buys you, intuition wise, since it's already sort of intuitively clear that nondeterministic oracle queries are much more powerful (then again, I guess you could say the same about nondeterministic computing...)
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
Richard Karp: (Berkeley, unsure, P!=NP) My intuitive belief is that P is unequal to NP,
but the only supporting arguments I can offer are the failure of all efforts to place specific
NP-complete problems in P by constructing polynomial-time algorithms.
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.
>> My intuitive belief is that P is unequal to NP, but the only supporting arguments I can offer are the failure of all efforts to place specific NP-complete problems in P by constructing polynomial-time algorithms.
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.
Sure, in some cases (the easy ones) we can solve NP-complete problems. However, tons of useful instances of NP-complete problems are not particularly close to being solved. We can even characterize fairly well when the instances become hard (for instance, for graph problems the treewidth seems relevant). I see absolutely no evidence that we're anywhere close to constructing a polynomial-time algorithm for any NP-complete problem. If anything, we are slowly finally making some progress on proving P != NP because we are finally getting some nontrivial superlinear bounds on these problems (thus far, the biggest obstacle to proving P != NP has been the difficulty of proving anything about lower bounds on runtime that isn't directly tied to space consumption).
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.
>> (thus far, the biggest obstacle to proving P != NP has been the difficulty of proving anything about lower bounds on runtime that isn't directly tied to space consumption)
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.
To be clearer, a trivial lower bound is something like "the input is of size n and for any n-1 length yes-instance you can find n-length extensions that are no-instances, so you have to check all n elements." It doesn't tell us anything interesting about the worst-case problem complexity. What's been surprising is how hard it is to make meaningful lower-bound statements stronger than that (well, not surprising to people who work on this stuff for a living, I guess). But that doesn't make it more likely that P = NP, really, except in the sense that we (obviously) haven't characterized the entire space of problems in P yet.
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.
It's true that there has been a lot of practical progress and even theoretical progress, though often of the form "we improve 1.8^n running time to 1.65^n". But...
> 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.
>> complete absence of progress in proving P != NP
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.
>> 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.
NP hardness is defined in terms of worst-case hardness, not average case hardness. As long as there exists even one instance that makes your algorithm take non-polynomial amount of time to terminate, P won't be equal to NP.
That's why I'm becoming increasingly skeptical of the usefulness (in the scientific sense) of complexity theory as it's currently laid out.
We already know that instances of NP-Hard problems are either easily solvable, in poly-time, or take exponential time, depending on the location of the instance in the problem space.
For example in SAT, the distance of the instance to the critical clause/variable threshold.
In subset sum, the density of the instance.
For those that do not have time to read the whole thing, #29 is worth quoting:
"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.
Reference needed:
Once upon a time Turing Machines were my thing. But that was decades ago. Now I think I have a result that's interesting, following up on graduate school work I did way back when... but... reading such things as the P=NP prize problem definition I see that at least some terminology in the field has changed, or at least, concepts have been added. (Such as "language", if I remember rightly.) Can someone point me to sources that will allow me to translate Turing oldspeak into Turing newspeak, and vice versa?
If investigating a specific result, I would recommend Wikipedia, ComplexityZoo and yes, even CSTheory.StackExchange. There are more comprehensive documents, however (re)learning a field may be an overinvestment to test a single idea.
Wikipedia won't have an entry on every specific problem, but it can come in handy if there's a general idea of what to search for. A quick investigation on "language" reveals "Formal Language" and "Model Theory" are relevant topics.
> 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.
Generally speaking, if there's a step that isn't clearly logically justified in your proof, the proof is considered wrong. So in most "normal" proof systems, this wouldn't really be a valid technique (that is, the moment someone tried to formalize it they'd run into this roadblock, and if it wasn't trivial to surmount the original proof would be thrown out). That said, there are some sequent calculi where you can do a lot of work in each step, so it might be really hard to figure out whether the step was valid; but I believe cut elimination theorems in those calculi basically assert that you can turn any valid "large step" into a (possibly very long, but finite) sequence of "small steps".
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.
Not a lot of mention of AI for CS, even in 2002. What about (2080+, P/=NP, proof techniques completely opaque to humans).
And by that I don't mean mechanical exclusion of special cases like for map-coloring. As mentioned already, there's like a handful of people that understand the FLT proof, that situation is unlikely to improve.
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.