The P-versus-NP Page (2016) | Hacker News Reader

The P-versus-NP Page (2016)

win.tue.nl

74 pointsrfreytag50 comments

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

Love this :)

Can't lose with that argument, eh? :)

Sorry. Too many experiences to really buy the logic "it can be done, it has not been done, hence contradiction". Indeed e.g. the proof of Fermat's theorem (Wikipedia: After 358 years of effort by mathematicians, the first successful proof was released in 1994 by Andrew Wiles, and formally published in 1995; it was described as a "stunning advance" in the citation for Wiles's Abel Prize award in 2016.) would be a contradiction of that logic. (Indeed, I am very confident that mathematics is a much more developed a mature field then IT).

The only time such an argument had been yielded and has some value is in my (not so, I guess) humble opinion when I think Fermi used the argument that if there was a lower energy level of water there surely would have been an animal by now that used this extra energy by converting water to this state (although I cannot find a link to this quite so quickly, so perhaps the argument was slightly different).

It's a joke, not a proof. I thought it was funny.

I'm very confident that orders of magnitude more man-hours have been spent thinking about P=NP in the past 20 years than were spent in the whole 358 years on Fermat's theorem. The number of people in academic situations to work on hard problems has increased exponentially.

I think it's fair to assume that there are potentially asymptotic limits to what can be achieved, but it's not that we default to one conclusion or the other, but that we conclude that whatever might be the real solution, the complexity of the proof is insurmountable or doesn't exist.

First off, it's a joke explanation and not meant to be taken seriously anyways.

But more notably, like Fermat's theorem, we can probably conclude that there's no easy quadratic or cubic algorithm for SAT that we've somehow missed. If P = NP, then, the most likely algorithm we'd see would be some hideous combinatorial algorithm that has a constant factor of 3^2^2^4 lurking in it that is completely impractical.

But it makes no sense.

P doesn't mean fast, it means polynomial.

A runtime of O(n + a) is polynomial (and just O(n)!), but with a big enough "a" (e.g. 2^999999999999999999999999999999999) it's likely large enough to be practically non-commutable.

I.e. there are "practically non-commutable" polynomial algorithm.

So the idea "there is not proof because we should have found it else wise" is deeply flawed.

Of course it makes no sense, it's a joke.

FWIW, it hardly matters, as the antecedent--the existence of a competent computer scientist--is unlikely at best.

I’ve tried a few times to understand what P=NP means and never felt like I understand what it’s about.

I get that problems can have constant/linear/polynomial/exponential complexity to solve so I (think) I understand ‘P’.

Over at NP I get confused around what constitutes a test/validating that a solution is true in polynomial time.

For example, a problem, “what’s the shortest path between two points” I get that a brute force breadth-depth first algorithm is going to rapidly take longer as more branches are added, but what constitutes verifying the solution?

In that example does verifying a solution mean having access to some prior list of all possible permutations and sorting them to find the shortest path, and because sorting is easy then this is an example of easily verifying?

To verify the shortest path, you would need to compute all the other paths as well, to be sure. so this doesn't sound like NP-complete

This confusion is caused by the different notions of problem: there are "decision" problems and "functional" problems. What grandparent asked ("what is the shortest path?") is a functional problem in nature, whereas P & NP are classes of decision problems. A (more or less) equivalent decision problem version of above question would be "is there a path of length at most X?", which then is of course easy to verify if a potential solution is presented.

Strictly speaking, NP problems need to have boolean outcome, so "what's the shortest path" is not an NP problem. Instead, "is there a path with cost <= X?" is an NP problem.

Of course, if I had a polynomial-time solver for the "cost <= X?" query, I could easily create a polynomial time solver for the cost of the shortest path, using binary search.

See Decision Problem: https://en.wikipedia.org/wiki/Decision_problem

There's a lot of handwaving in practice over complexity classes. Strictly speaking, P and NP only consist of decision problems, that is, the expected output is solely "YES" or "NO". In practice, however, we mostly care about functional problems, ones that give a result. Your example of "what's the shortest path between two points" is such an example: the decision variant is "is there a path between two points less than k?"

The general process to convert a function problem of "find the best X for this input" to a decision problem is to recast it as "is there an X better than k for this input?" So the validation in these cases means finding that a) the claimed X is actually an X on the input (e.g., a sequence of nodes to visit is actually a valid path in the first place), and b) you can measure the property of X you're trying to optimize (e.g., what is the total cost of the path).

Another way to think of it--one which actually illuminates the underlying proofs a bit better--is that NP is a nondeterministic class. Basically, this means that any problem in NP [in the fuzzy sense] can be thought of as a polynomial-time algorithm, but every time we have to make a "choice" of some kind (which node to pick next, which color to assign it, etc.), we can ask a magic oracle which tells us the correct answer in O(1) time.

and NP only cares about being able to verify YES answers. co-NP cares about verifying NO answers. It's unknown whether or not NP and co-NP are equal.

> Your example of "what's the shortest path between two points" is such an example: the decision variant is "is there a path between two points less than k?"

Just to add to this: This can obviously also be brought back to "find the shortest path", by just asking the question again and again for smaller and smaller k, by halving.

If you are genuinely interested in understanding this, I would be interested in helping you get there. I'm not an expert, but when I've spoken with people who are experts, they have told me that I'm getting things right.

An email address that works for me is in my profile.

NP are the problems which we can verify an answer to 'quickly'.

P are the problems that we can create an answer to 'quickly'.

The question is, if we are able to verify an answer quickly, does that imply we can also always create an answer quickly? It feels like obvious not the case, but we can't prove it either way.

One fun fact is that Sudoku (on a n by n grid) is NP-complete.

It's in NP because given a sudoku problem instance (a n by n grid with only some clues filled in) and a proposed solution (a n by n grid with all the squares filled in) you can check if the solution is correct in polynomial time. That is, you check that each square in the problem is equal to the square in the solution, and you check the rows/columns/larger-squares to see if they each contain the values (1..n).

So a problem X is in NP if given a polynomial-sized certificate C, you can run a polynomial-time algorithm C_Check() to see if it is actually a valid solution. In the sudoku problem:

X is Sudoku with instance x C is the proposed solved sudoku C_Check(x, C) is the algorithm where you check the rows/columns/larger-squares and you check that for every square in X[i][j] that is filled, C[i][j] == X[i][j]

In a normal breadth first search, where there are a polynomial # of vertices, you actually don't even need to use C until the very end. You're allowed to say

X is ShortestPathProblem with instance x C is the proposed shortest path C_Check(x, C) is just (BFS(x) == C)

So therefore any problem in P is automatically in NP.

> For example, a problem, “what’s the shortest path between two points”

Switching to the decision version: "Is there a path of length at most L between the two points?"

To verify a "yes" answer, you get a path; and you just verify that it's short enough and goes from the first point to the second; that's it.

Obviously this verification doesn't work for a "no" answer.

The link to Scott Aaronson’s “Is P vs NP Formally independent” actually points to his broader survey of P vs NP. Here is a link to the one about independence http://people.cs.uchicago.edu/~fortnow/beatcs/column81.pdf

Both are enjoyable reads.

Linked on the page is an opinion poll [0] with responses from some prominent mathematicians (including Shor, Conway and Knuth). I thought it was really interesting to hear their thoughts on the problem.

[0] http://www.cs.umd.edu/~gasarch/papers/poll.pdf

Conway didn't care much for it, did he:

> (P!=NP) In my opinion this shouldn’t really be a hard problem; it’s just that we came late to this theory, and haven’t yet developed any techniques for proving computations to be hard. Eventually, it will just be a footnote in the books.

I wrote a German espionage novel about the topic, based on the idea that someone might have found a promising proof of P=NP. However, it got a pretty damning review. Maybe someone with better writing skills should take up the topic?

https://www.goodreads.com/en/book/show/37986693-factor-man

Damning review of your book, or damning review of the proof?

... Anyway, awesome pun!

Was P=NP just an arbitrary McGuffin, or did the proof actually have plot ramifications?

No, not arbitrary. It could have been any other technique or proof that potentially makes breaking ciphers easier, but the idea in the novel is that the proof might have constructive applications or could at least lead to them, and the mathematician who developed it is specialized in the topic and not a crackpot. The decisive factor for the plot is that other agencies want to have it, though.

It's never said explicitly, but I believe the McGuffin in the movie Sneakers implies its inventor has either found a proof of P=NP or has implemented an algorithm that would imply a proof of P=NP.

I like Knuth's take on that matter, saying that P=NP and that it doesn't really matter. The space P is huge and still virtually unexplored. There are extremely powerful algorithms inside O(n^googol), and this is just barely scrapping at the bottom of P.

Quick stats:

[Equal]: 62

[Not equal]: 50

[Undecidable]: 1

[Unprovable]: 2

Is [Unprovable] the same as [Not equal]? It seems like the only way that's possible is if P!=NP, since in the other case there's just so many proofs available (proofs be example, algos that solve any of several hundred known problems in poly time). So in a sense, any proof that there is no proof would be proof that P!=NP. Maybe I'm missing something?

I think it means that neither P=NP nor P!=NP is provable.

But is it a proof that neither is provable? Or just a statement of giving up?

Assuming it's a proof, there's two cases: 1) it's really P=NP, but we can't prove it 2) it's really P!=NP, but we can't prove it

If it's case 1, that's impossible. If P=NP, then there exist polytime algorithms for NP-Complete problems, and any of those algorithms are a proof that P=NP. So that's a contradiction.

So the _only_ possibility given a proof that it's unprovable would be case 2, thus proving P!=NP and contradicting itself.

Am I missing something? Even assuming I'm right, this isn't a proof that one of P=NP or P!=NP are provable, just that it's impossible to prove that neither can be proven.

Math proofs start given a set of axioms. The modern set of Axioms are ZFC. If you can find a new axiom A such that ZFC + A is a consistent system[1] and P=NP, and also find a new axiom B such that ZFC + B is a consistent system[1] and P!=NP, then logically, P?=NP cannot have a solution either way in just ZFC.

[1] Assuming ZFC is itself consistent

Are Turing machines representable in ZFC (pretty sure they are)? Seems like it'd be at least _really_ difficult to do that trick if so.

That would mean that in ZFC+A there exist algorithms that can't exist in ZFC+B? Hard for me to imagine what those would even be, since they'd have to be representable in ZFC itself anyway, right, since that's all that an algorithm would be this model, a particular Turing machine?

Yeah, there's a reason most people don't think it's independent. Still, there are a significant number of things that are independent:

https://en.wikipedia.org/wiki/List_of_statements_independent...

But (I think) all of them have to do with infinity in some weird way.

Not sure if this applies here but generally speaking, there are things that are true but unprovable. See Gödel's Incompleteness Theorem [1].

[1] https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_...

Good callout, thank you. Yeah I'm aware in general that there are unprovable true things. I've somehow convinced myself that this can't be one of them, though the other thread of this I believe I'm being shown how it might be.

No, it's possible that there is a P-time SAT-solving algorithm A, but that it's not provable that A runs in P-time, and/or it's not provable that A actually solves SAT (even though it does).

In fact there is a known and fairly simple algorithm that provably solves SAT, but its running time is unknown. It runs in P-time if and only if P=NP. It is called Levin's Universal Search and you can read about it.

I'm assuming that's the stats for the "results" on the linked page. It's certainly not the stats of opinions of mathematicians in my circles.

Why are the examples for P≟NP always so bad? "Solving TSP", "planning airlines better", "get the $1M bounty"?

Why not SAT? There's a $200,000 bounty paid out every ten minutes for solutions to a well-known SAT problem.

Or crypto. Math. Chess.

Chess isn't NP, is it?

> There's a $200,000 bounty paid out every ten minutes for solutions to a well-known SAT problem.

I'm not sure I follow -- do you mean there is a challenge open somewhere which pays 200k$?

Bitcoin. Bitcoin relies on SAT being unsolvable.

The payout is pretty great.

Solve SAT.

Short the hell out of bitcoin.

Release solution.

Solve SAT. Mine 1 block each day. Sell.

That's a great way to make millions instead of billions.

chess is EXP

> There's a $200,000 bounty paid out every ten minutes for solutions to a well-known SAT problem.

I don't think I would describe SHA256 prefix matching as "a well-known SAT problem".

Reply on news.ycombinator.com