Hacker News Reader

Comment by kibwen | Hacker News Reader

Is it possible to prove that a proof exists for either P=NP or P!=NP? Conversely, is it possible to prove that the conjecture is unprovable?

View on HN

When people try to use 'NP complete' as a dodge for doing difficult coding at work, I point out to them that Claude Shannon proved that generalized compression algorithms can't exist, and yet we are surrounded all day by compression algorithms.

Just because the space in NP hard doesn't mean that your problem is automatically NP hard. Lots of human consumable or generated data is full of patterns that can be exploited to useful purpose, even when purely random inputs are intractable.

>[...] I point out to them that Claude Shannon proved that generalized compression algorithms can't exist [...]

What proof are you talking about?

They just mean that there is no general way to compress an arbitrary M-bit string to an N-bit string for M > N, and yet compression algorithms exist.

The point is that the input to your compression is not an arbitrary M-bit string, but some very structured thing which could have a smaller representation. Similarly, when encountering what appears to be an NP-hard problem in the wild, you might still be able to find an efficient solution by exploiting the structure of your input (NP-hardness only applies when considering all inputs).

One major issue is that the quote seems entirely backwards. In fact, Claude Shannon described how to optimally compress a string from a known source. https://en.wikipedia.org/wiki/Shannon%27s_source_coding_theo... As such, Shannon's results would suggest the existence of many compression algorithms.

(And conversely, I see no reason to believe that "Claude Shannon proved that generalized compression algorithms can't exist". I assume that result predates Shannon.)

The pigeonhole principle establishes that you cannot fit n distinct messages into m spaces, where n>m

The Shannon coding limit defines the bounds on what subset of n can fit into a channel of capacity m, without excluding any of the others.

By drawing a fence around the possible, he fences out the impossible.

comp.compression has several longstanding bets that one particular high entropy input can not be represented by any decoder smaller than the difference in the input and output size, but I lack their confidence in the infallibility of their entropy source. It is possible someone will win that particular bet, but there will come a time where another similar bet will never be collected.

Yes, and yes. P != NP could be independent from Peano Arithmetic (PA) or the Zermelo-Fraenkel set theory with Axiom of Choice (ZFC) models. That is a separate conjecture which is also presently open.

Surprisingly, this cannot be the case, not without discovering a completely new kind of independence proof. [0] p26 discusses the problem.

> At the end of the day, a polynomial-time algorithm for 3-SAT either exists or it doesn't!

[0] https://www.scottaaronson.com/papers/pnp.pdf

Since an algorithm for running NP-complete problems in P-time would be enough to prove whether P=NP, wouldn't the impossibility to prove it just prove that P!=NP?

Not really, we don't know if human reasoning is contained in P, BPP, BQP, PP or even PSPACE (is there a ghost in this shell?). It may not be. Though human reasoning probably is contained in P, just like probably P != NP.

Human reasoning is constant time. Generalized unbounded humanlike reasoning might not be.

You could perhaps have a program that for every input you've tried gives the correct answer in polynomial time, but you haven't yet proved that it always will.

Nevertheless, I don't see how the answer to P!=NP could depend on the choice of axioms for set theory. Programs, their inputs and the state of a machine after executing n steps can all be encoded as integers, so P!=NP can be expressed as a statement about integers, and we know what the integers are: we don't need any dodgy set theory axioms for that.

If that's wrong, someone please explain how.

There are lots of interesting unsolved questions about integers (Goldbach's conjecture, ...) but people don't usually suggest that the answer to those questions might depend on the Axiom of Choice. Or do they?

Surprisingly, a theorem being unprovable does not mean that the theorem is untrue, even if you can prove its unprovability! This was shown by Goedel (https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_...). He showed that there exists no system powerful enough to express theorems about the natural numbers which can prove all facts about natural numbers and be sound (ie not prove things that are untrue).

That's not exactly what I'm saying. What I am saying is that it's impossible for it to be true and unprovable. If it is true, it means a proof exists.

Also, I am talking about this specific problem.

Can you prove that?

"impossibility to prove" is different from "proven impossible" because hiding behind the loose English are different models of logics. That's what Godel theorems at e about.

It is possible to be true and unprovable. Truth does not imply provability (the reverse does hold).

Gödel's statement, which essentially says "I am unprovable" is an example of a true, unprovable statement.

Reply on news.ycombinator.com