[HN Gopher] P vs. NP and the Computational Complexity Zoo (2014)...
___________________________________________________________________
P vs. NP and the Computational Complexity Zoo (2014) [video]
Author : kl4zo
Score : 114 points
Date : 2024-04-29 18:05 UTC (1 days ago)
(HTM) web link (www.youtube.com)
(TXT) w3m dump (www.youtube.com)
| dang wrote:
| Related:
|
| _P vs. NP and the Computational Complexity Zoo (2014) [video]_ -
| https://news.ycombinator.com/item?id=9596496 - May 2015 (53
| comments)
| datascienced wrote:
| 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 wrote:
| FWIW, LLMs are currently stomped by the "mere" N^2.
| datascienced wrote:
| 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 wrote:
| Wake me up when the "exponentially increasing computers" can
| multiply two matrices in O(n^2.371552)
| deepnet wrote:
| This is a very clear and extensive explanation of the hierarchy
| of difficulty.
| tromp wrote:
| 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 wrote:
| Translating a new problem to any problem that has already been
| proven to belong to that complexity class suffices.
| Daimanta wrote:
| 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.
| andrewflnr wrote:
| 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.
| mehulashah wrote:
| 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.
| JohnMakin wrote:
| 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 wrote:
| my theory is that we'll prove that its impossible to prove
| whether or not P = NP.
| Maxatar wrote:
| If P = NP is undecidable in ZFC then it necessarily follows
| that P != NP.
| vecter wrote:
| Can you explain why?
| Maxatar wrote:
| 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.
| mehulashah wrote:
| 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 wrote:
| 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.
| nyrikki wrote:
| 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.
| mehulashah wrote:
| I don't understand this. Can you give me some pointers so I
| can research it myself?
| nyrikki wrote:
| 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.
|
| Godel is another lens, but the difference between syntactic
| and symantic completeness causes problems. As well as Godel
| 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.
| Phiwise_ wrote:
| 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 wrote:
| 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 wrote:
| 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-rash wrote:
| 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 wrote:
| 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.
| basil-rash wrote:
| 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.
| andrewflnr wrote:
| 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.
| basil-rash wrote:
| 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.
| gmd63 wrote:
| 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?
| andrewflnr wrote:
| 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 wrote:
| 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 wrote:
| 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.
| JohnMakin wrote:
| 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.
| Laakeri wrote:
| 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.
| Maxatar wrote:
| 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.
| Laakeri wrote:
| 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".
| jltsiren wrote:
| 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 wrote:
| > 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
| b-side wrote:
| 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 wrote:
| Because that's not the framework where N and NP applies. There
| is no notion of black boxes outside of the algorithm.
| adgjlsfhk1 wrote:
| there is an O(n) Turing machine that guesses only the correct
| binary number. you just don't know which.
| teraflop wrote:
| 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 wrote:
| 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 wrote:
| 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.
| supernewton wrote:
| 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.
___________________________________________________________________
(page generated 2024-04-30 23:02 UTC)