P vs. NP and the Computational Complexity Zoo (2014) [video] | Hacker News Reader

P vs. NP and the Computational Complexity Zoo (2014) [video]

youtube.com

131 pointskl4zo53 comments

One subtlety this video skips over, is that P and NP are defined as classes of decision problems, rather than arbitrary computational problems.

So when they talk about the problem of finding the number of moves it takes to unscramble a Rubik's cube, you need to translate that into a decision problem in order to place it into one of these classes. If you can then solve the decision problem efficiently, you should be able to use that to solve the computational problem efficiently.

That could be: given a Rubik's cube and an integer k, is it possible to unscramble it in at most k moves.

When the problem is to find the discrete log of a curve point on an Elliptic Curve, the decision version could be: given a point P on a curve of order < 2^n with generator G, and a bitstring x of length at most n, is there a n-bit number k with prefix x such that P = xy * G ?

Translating a new problem to any problem that has already been proven to belong to that complexity class suffices.

It's the other way around. Translating a problem with a known complexity class to the new problem(in time P) indicates the complexity class.

They explicitly swept all the differences between different NP-complete problems under the rug as "some polynomial-time complexity", so I don't think he's worried about the translation between decision problems and others. He's trying to explain the broad significance of P vs NP for non-computer-scientists, so I'd agree that level of "subtlety" isn't necessary. Someone who cares and puts in the effort won't have a problem taking that in stride if they want to learn the full version later.

Ten years and this is probably still the best layman-level explanation of P vs NP out there. It blew me away as my introduction to the subject at the time. Such a shame Hackerdashery didn't keep making videos, especially since the mathematical explainer segment was so much smaller at the time.

If you like this, you might also like his only other upload, on Haskell Curry'd book on mathematical philosophy and the foundations of set theory: https://www.youtube.com/watch?v=AmySxYHqQCQ

P vs. NP and the Computational Complexity Zoo (2014) [video] - https://news.ycombinator.com/item?id=9596496 - May 2015 (53 comments)

In reality if you have O(N^1000000) that is still going to be a killer for our exponential increasing computers. For any N you can wait for computation to catch up but N*2 will stomp you for quite a while.

FWIW, LLMs are currently stomped by the "mere" N^2.

Sure that is indeed true!

I meant polynomial time can in practical terms stomp computers even if you are allowed to time travel to a future point in moores law. Maybe n^2 is enough but need to do the math! The derivative is 2n so seems like it depends on n and the problem and of course the constants.

Or maybe human life is just too short to wait for the “42”

Wake me up when the "exponentially increasing computers" can multiply two matrices in O(n^2.371552)

Sure, but in practice there don't really seem to exist "natural" problems that are both in P and are worse than O(n^3) or so.

By "natural" I mean a problem that one would actually want to solve, not some contrived problem specifically to make it O(n^100) since that's obviously easily possible.

I always wondered how the following setup does not prove that NP != P so please chime in.

Finding the correct N-bit long (binary) number (that someone is thinking of, they only reply yes or no to a guess). Verifying if the number is correct can be done in Polynomial time yet finding the correct number can only be achieved by trying (brute force) all the 2^N possibilities?

Because that's not the framework where N and NP applies. There is no notion of black boxes outside of the algorithm.

there is an O(n) Turing machine that guesses only the correct binary number. you just don't know which.

For P vs. NP to apply, you would have to be given a Turing machine (or equivalent program) that could verify a guess in polynomial time, without having to ask somebody.

But how do you know that Turing machine couldn't be somehow reverse-engineered to find the number without trying every possibility? You don't know, you're just assuming it. Proving that assumption is the entire point of the problem.

From watching the linked video, and going by the given informal definition for NP-Problems "hard to compute, easy to verify" I think of it this way: You can not compute the secret number efficiently, only the keeper of the secret knows it. So the number is indeed hard to compute. But can you easily verify a solution? Sure you can ask the keeper and he can tell you the answer, but then you didn't verify it yourself. If you count on the secret keepers cooperation he could also just tell you the number, making it easy to compute.

NP means, a solution can be found in polynomial time with a hypothetical non-deterministic Turing machine.

If your problem statement includes the number to be guessed, it's trivial and solvable in linear time without non-determinism.

If it does not include the number to be guessed, then the process of "verifying the solution" has no access to this info by definition too, and it is not possible to verify the solution at all!?

Apart from that, the verifiability of a solution in polynomial time on a deterministic Turing machine is a necessary consequence of a problem being in NP, but the reverse direction does not apply without additional conditions, IIRC.

If you want to say anything interesting about related problems in regard to complexity theory, you'll have to introduce an "oracle".

As far as my knowledge goes, even this doesn't make the problem of "guess an unknown number" without further qualification more interesting.

Maybe it would be a good exercise to apply these ideas to binary search for an unknown number, with the answer (greater, smaller, correct) as an oracle. Of course the number must be computable, which doesn't preclude it from being transcendental. Another interesting rabbit hole :)

It looks as if you exclude any numbers with an infinite decimal representation by allowing an oracle that says "yes" or "no" to a guess — but of course numbers can also be defined using different means, e.g. convergent sum series etc — and we both know that Pi is finite, right?

A formula that can calculate Pi to an arbitrary precision is a finite and complete representation of Pi, just not as a sequence of digits.

Digging further into this would lead away from CS and into Maths, particularly there are old and new discussions about the "existance" of transcendental numbers (irrational would suffice, too). This is a part of our shared scientific basics, at least in any math-adjacent field.

Googling "Nicolas Bourbaki" is at least as interesting as the complexity theory zoo :)

But probably I'm going over my head here since I don't know much about complexity theory apart from faint CS course memories about Cook's theorem.

You don't get to have "hidden information". The code used to respond "yes" or "no" to the guess would be part of the problem input. But, we currently can't prove there doesn't exist some algorithm that can examine that code and figure out what the "yes" input is faster than brute forcing all inputs.

This is a very clear and extensive explanation of the hierarchy of difficulty.

For an overview of other complexity classes besides P and NP, there's https://complexityzoo.net/

I like primers like this but in an attempt to boil it down it misses a sublety - that being that "P" is defined here as a problem a computer can solve "quickly." When really, the class of problems in P are just able to be solved in polynomial time. You could write an algorithm that is O(n^50) that technically is in P, but a computer would take practically forever to solve. Also, there exist problems that are NP hard that cannot be solved in polynomial time and have atrocious worst-case complexity, but their average complexity is quite reasonable and feasible for a machine to calculate.

A kind of nitpicky distinction, but this is such a common misunderstanding.

I'm not sure if its really misunderstanding, when in 99% cases it has turned out that if a problem is in P, then it has a polynomial-time algorithm with a quite small exponent.

I feel like your claim is begging the question.

It's certainly not true in principle that most problems in P have a small exponent. There is no shortage of graph related algorithms in P that have absolutely absurd exponents, like on the order of 10^100. It is true that practical decision problems that are in P have small exponents but that's exactly the point being made, namely that problems in P with large exponents are not practical and hence don't get much attention.

What are examples of natural graph related problems in P with absurd exponents? I think the reason they don't get attention is not that the algorithms are not practical, but that the problems are not natural. Really, the only examples of such problems I can think of are something like "Finding a clique of size 222222 is in P because we can try all possibilities in n^222222 time".

As the amount of data grows, exponents that used to be small become large.

In many applications, the data grows at least as quickly as computer performance. If the fastest known algorithm is superlinear, today's computers take longer to solve today's problems than yesterday's computers solving yesterday's problems. While O(n^2) time algorithms used to be pretty fast in the 80s, today they are often unusable.

I completely agree with you. My point was that the P vs NP distinction matters in practice, but of course also the subquadratic vs quadratic time distinction matters a lot.

> Also, there exist problems that are NP hard that cannot be solved in polynomial time and have atrocious worst-case complexity, but their average complexity is quite reasonable and feasible for a machine to calculate.

This is an active research topic of trying to characterize worst-case assumptions (i.e., the traditional kind) that imply average-case hardness for some problems, with several recent exciting results. See, for instance, an excellent talk here: https://www.youtube.com/watch?v=aQZEsmpbWE0&t=578s

Great talk thanks for the link!

My bet is on P = NP. A proof will be found, but it will not be constructive. We will need the help of deep learning models to “discover” the contradiction. Then, the fun will begin.

I believe the consensus among prominent computer scientists is that P != NP. I'm not really too sure how deep learning models will solve this.

my theory is that we'll prove that its impossible to prove whether or not P = NP.

If P = NP is undecidable in ZFC then it necessarily follows that P != NP.

Can you explain why?

Assume that P = NP is undecidable, then it would not be possible to present an algorithm that is NP-complete and in P, since such an algorithm would imply that P = NP is decidable which contradicts the assumption that P = NP is undecidable.

A simpler way to think about this concept in general would be, assume that it's undecidable in ZFC whether every even natural number greater than 2 is the sum of two primes.

Well if it's undecidable in ZFC then it must be true. If it weren't true then it would be possible to present an even number that isn't the sum of two primes, but presenting such a number would be a proof and hence contradict the assumption that it's undecidable. Hence the only way for it to be undecidable in ZFC is if there isn't any such even number, but ZFC is not powerful enough to prove that no such number exists.

This is the subtle difference between decidability and truth. For certain classes of statements (not all), especially ones involving existence, if they are undecidable within ZFC then they must be true.

Another subtlety is that one can never state categorically that a statement is undecidable, a statement can only be undecidable with respect to a formal system, and being undecidable with respect to a formal system does not mean that we can't ever know if that statement is actually true or false, it just means that said formal system is not powerful enough of proving from within that system whether it's true or false.

What if you had an algorithm which could e.g. solve 3SAT in polynomial time, but couldn’t be proven (in ZFC) to always produce the correct answer?

If you can prove in ZFC that the algorithm always halts for every input but it's undecidable in ZFC whether the algorithm is correct for every input, then it follows that the algorithm is correct for every input and hence P = NP. If you can't prove in ZFC that the algorithm halts for every input then you can't deduce anything further. Let's break it down and get an understanding of why this is.

Assume an algorithm X halts for every input and it's undecidable in ZFC whether X is correct for all inputs. Well if X were incorrect for some input Q, then since X halts for every input, Q could be used to prove in ZFC that X is incorrect. Since we assumed that X's correctness is undecidable in ZFC, it follows that no such X exists.

To better understand the nature of this issue, it boils down to the fact that ZFC can not unambiguously define the natural numbers. For every definition of the natural numbers in ZFC, there are at least two possible interpretations, one interpretation is the actual natural numbers 0, 1, 2, ... where every single natural number consists of a finite sequence of digits. But ZFC will also have another interpretation of the natural numbers which are not the ACTUAL natural numbers but a kind of mutation of the natural numbers, these natural numbers can have an infinite sequence of digits.

In situations where the correctness of an algorithm is undecidable in ZFC, it means that there is some interpretation of the natural numbers, some mutated system of numbers where the algorithm would give the wrong answer. The algorithm gives the correct answer for all ACTUAL natural numbers, but will give an incorrect answer for some mutated "natural number" consisting of an infinite sequence of digits. Because ZFC is not powerful enough to distinguish between the actual natural numbers and the mutated natural numbers, ZFC is not powerful enough to prove that the algorithm is correct for the actual natural numbers.

You can read more about these mutations here:

https://en.wikipedia.org/wiki/Non-standard_model_of_arithmet...

Now you might think that 3SAT isn't about natural numbers, the input for 3SAT is a boolean formula, not a number. Well that's a minor detail since for every single boolean formula, there is a 1-to-1 correspondence to a natural number. So this hypothetical algorithm would be correct for every formula that has a correspondence to an actual natural number, and each of these formulas would consist of a finite sequence of symbols, ∨, ∧, ¬. However, there would also be mutated versions of these formulas that don't correspond to a natural number but do correspond to a mutated natural number. These formulas would consist of an infinite sequence of symbols, ∨, ∧, ¬. Since the algorithm is undecidable in ZFC, then there is some mutated formula for which the algorithm gives an incorrect answer and since ZFC can not distinguish between mutated formulas and actual real formulas, that's where the undecidability lies.

And finally, you may be tempted to think that you can just define the natural numbers in such a way that they must consist of a finite sequence of digits and this whole issue will go away, surely there must be some way we can define the natural numbers so that they consist only of a finite sequence of digits and rid ourselves of these infinite sequence mutations. And well what we know from Godel's incompleteness theorem is that there is a way to do that, but it involves making your system inconsistent.

If X runs in polynomial time, then there is of course some X' which produces the same outputs on the same inputs, and provably (in PA, I'm pretty sure, certainly in ZFC) runs in polynomial time. So, if there exists an algorithm X which solves 3SAT in polynomial time, then there is an algorithm X' that provably runs in polynomial time, and solves 3SAT. If ZFC cannot prove that X' always produces the right answer, then, I suppose that implies (By Godel's completeness theorem) that there is a model of ZFC in which it doesn't...

uhh... huh.

Does the standard construction of the natural numbers in ZFC, if considered in a non-standard model of ZFC, produce a nonstandard model of PA? That's not what I had expected.

err... I guess there isn't necessarily a thing which is considered "the standard model of ZFC", so I guess I mean, "is there a model of ZFC in which the usual construction of the natural numbers, isn't the standard model of the natural numbers?" (where the model of ZFC is I guess a model within another ZFC or some other set theory, and asking whether the set of natural numbers in that model, is the standard one, is asking about how it compares to the model of the natural numbers in the outer set theory)

Certainly, I’m not an expert and the experts believe generally believe P != NP. That’s why they spend their time trying to prove it. They also spend time trying to prove that we will never know. There’s comparatively not much effort given to prove the opposite. See the opposite doesn’t mean all problems are easy. They could still be hard, e.g. N^M with a really large M. In addition, we often prove things by contradiction. Wouldn’t it be interesting if the proof by contradiction involved finding a solution to another hard problem that today we cannot easily find. Deep learning models trained and scaled on instances of the subproblem may be able to help us do that.

Anyway, it’s just a thought. Think of it as complexity-poetry.

There are notable exceptions, Donald Knuth, for example, is on the P=NP side of the divide but thinks the proof might be non-constructive or that the runtime might have some completely impractical power. I think he cited the Robertson–Seymour theorem and pointed out that there is a gigantic space of polynomial time algorithms with big powers that nobody has explored.

If you approach it from Fagin’s Theorem, which provides that NP == the set of existential second order boolean queries, NP = SO∃. Even when the first order part is universal...you will see how the P=NP question will probably never be solved.

To be clear, we absolutely need optimists to keep looking at it and learning more.

But the way it is taught often makes it seem like proving or disproving P=NP is just a matter of time, when the safe bet is that it will never be solved.

I don’t understand this. Can you give me some pointers so I can research it myself?

Look at the SO entry on complexity zoo.

existential quantifier: “there exists an x such that...”

universal quantifier: “for every x such that..."

NP is the truthyness of yes-instances

co-NP is the truthyness of no-instances

P=co-P but we think NP!=co-NP

NP is the same as a second order logic with an existential second order part.

co-NP is the same as second order logic with a universal second order part.

Consider how the following two are different:

“there exists an x such that there exists a y such that...”

“there exists an x such that for every y such that...”

That is an oversimplified bad example, but set theory, logic, and complexity are were to start.

Gödel is another lens, but the difference between syntactic and symantic completeness causes problems. As well as Gödel dealing with TMs and not the physically unrealizable NTM.

Proving P=NP would have the implication that NP=co-NP

Proving P!=NP would prove the opposite.

IMHO the most likely lottery winning outcome is that we prove that we can't prove P=NP, but that would cause other issues.

More likely we will have to accept the limits of computable proofs and have an unsatisfying result and the problem will stay open.

Nature herself seems to imply P != NP, as one can characterize evolution as a messy, computationally intensive "search" through a large space of "solutions" to a suitability problem. If P=NP one would expect some organism to evolve that can construct whatever arbitrary proteins, organelles, etc that it needs at any time.

Of course, it could be that humans, with AI and CRISPR, will soon become that organism, but it seems unlikely to me that this capability wouldn't evolve more naturally with fewer intermediate steps.

Why would assuming P=NP implies an organism could produce all things? The possible equality says very little about the order allowable in P, there.

Consider, we know that Game of Life is equivalent to a Turing machine. It still doesn't immediately follow that any program you write will be found in a Game of Life. Closest we have there, is folks are able to build a VM in it where they can make a program in another language that they can play in it. Realistically, they should be able to skip the VM phase, but I don't see that happening any time soon. (Oddly, this same example goes for traditional computers. Consider something like sorting networks and contrast them to how we usually sort numbers in a computer.)

That’s under the assumption that evolution works as taught in gradeschool. Under big-step evolution, no such contradiction exists.

Indeed the evidence would tend to point towards big-step being the primary mechanism of speciation (fossil gaps, bizzareness of many intermediary states), but this is such a strange proposition to folks who have a P != NP prior that they tend to dismiss it out of hand.

The contradiction is still valid in big step evolution.

Kind of like guessing a passcode to a lock. You still try all the combinations, but there are no intermediate steps - you either guess it all at once, or not at all.

If we see a bunch of locks opened by someone who couldn't have had the code, it doesn't mean they had a method to open. They could've just spent a lot of time guessing.

Indeed, we need to look at external factors like time/energy expenditure to determine the efficiency of the operation in order to have a hope at constraining its method. If the NSA were to suddenly publish a list of 1,000,000,000 broken SHA512 keys, and there was no sign of any spikes in energy expenditures, we could strongly suspect that they did not generate them from brute force means. Similarly, if we have hundreds of millions of distinct species on the planet, and only a few years of time on the planet (relative to the rate at which we've observed beneficial random mutations actually occurring), we can suspect that the bulk of the speciation did not occur through stochastic means.

Fossil gaps don't imply much except that fossilization is rare and dependent on conditions. And there's are definitely lots of well preserved, smooth transitions. I don't even know what you think "bizarreness of intermediate forms" implies, but it still looks consistent with small steps to me. Notably "bizarre" is a highly subjective judgement that really has no place in this sort of argument.

Granted, sometimes those small steps come faster than others, e.g. adaptive radiations. But there's still only so big a change you can make in a single generation that both doesn't immediately render the organism nonviable and gets through all the checks designed to prevent mutations.

Anyway, last I heard the biggest driver for speciation was just reproductive isolation, so unguided genetic drift can make the two sides incompatible.

The bizarre intermediary forms are specifically those that do not appear, and that would make no evolutionary sense to exist. Things like feathers. Now, evolutionists will come up with fanciful untested (untestable), unobserved (unobservable) narratives in attempt to jam such cases into their world view – and that's all well and good, I do the same. I just don't pretend to call my interpretation scientific, I call it religious/faith-based. They'd do well to do the same.

There likely isn't a problem defined by some metaphysical being or alien that's being solved for. And if there was, how would you assume that our current "search" isn't incredibly fast when compared to the alternative, whatever that would look like?

There's no strong reason to expect evolution to be optimal at anything. It's a process of gradient descent. If the particular thing you think it "should have" invented is behind too high a wall, oops, evolution never finds it.

And there's a high wall. Even if it's in P, calculating the structure of a protein from a functional goal is going to be energetically expensive on the scale of a cell. That's energy the organism could have used for eating or reproduction instead. And before that you have to biochemically represent goals for a protein, and match them with outside stimuli. More complexity, more energy. It doesn't seem worth it; life is already shockingly adaptable. Oh, and if you want arbitrary organelles, multiply all that by 10-1000.

This whole reasoning only makes sense if you take P to mean "easy to solve". In reality, P=NP would almost certainly not have any bearing on evolution or even computing. It's basically certain at this point that any polynomial time program that solves an NP complete program will have a large exponent, say it will be O(n^10), which for all intents and purposes makes it just as intractable as O(e^n).

P=NP is an extremely important and deep theoretical problem, but it is very unlikely to have direct practical implications.

I have always thought that the fact that Earth evolved human life in only 5 billion years is strong evidence against P ≠ NP, if anything. Unless "evolving a human being from scratch" is substantially easier than cracking an SSL key, anyway.

Reply on news.ycombinator.com