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

https://www.youtube.com/watch?v=YX40hbAHx3s

by kl4zo • 2 years ago

131 53 2 years ago

dang• 2 years ago

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

datascienced2• 2 years ago

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.

hnfong• 2 years ago

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

datascienced2• 2 years ago

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”

PhilipRoman• 2 years ago

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

supernewton2• 2 years ago

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.

deepnet• 2 years ago

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

tromp• 2 years ago

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 ?

nabla9• 2 years ago

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

Daimanta• 2 years ago

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.

andrewflnr3• 2 years ago

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.

mehulashah3• 2 years ago

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.

JohnMakin3• 2 years ago

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.

alectroem• 2 years ago

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

mehulashah3• 2 years ago

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.

danbruc• 2 years ago

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.

nyrikki2• 2 years ago

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.

mehulashah3• 2 years ago

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

Phiwise_• 2 years ago

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

javajosh• 2 years ago

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.

taeric• 2 years ago

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.)

basil-rash3• 2 years ago

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.

kolinko• 2 years ago

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.

andrewflnr3• 2 years ago

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.

gmd63• 2 years ago

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?

andrewflnr3• 2 years ago

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.

tsimionescu• 2 years ago

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.

ComplexSystems• 2 years ago

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.

JohnMakin3• 2 years ago

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.

Laakeri3• 2 years ago

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.

Maxatar4• 2 years ago

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.

jltsiren• 2 years ago

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.

ilya_m• 2 years ago

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

JohnMakin3• 2 years ago

Great talk thanks for the link!

b-side• 2 years ago

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?

planede• 2 years ago

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

adgjlsfhk1• 2 years ago

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

teraflop• 2 years ago

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.

baraah• 2 years ago

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.

moritzwarhier• 2 years ago

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.

supernewton2• 2 years ago

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.

mttpgn• 2 years ago

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

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

Related Stories