4 ms·
I hope nobody proves that "P!=NP" because that would just be too boring, too expected. I think the coolest possible outcomes would be one of the following: (a
by skissane 5y ago
I hope nobody proves that "P!=NP" because that would just be too boring, too expected.
I think the coolest possible outcomes would be one of the following:
(a) some bizarre algorithm which solves an NP-complete problem in polynomial time but with utterly intractable exponents or constants, for example worse than O(n^(10^100)) – so, yes, P=NP, in a completely useless way, and still nobody would know if a useful P algorithm for an NP-complete problem exists
(b) a non-constructive proof that P=NP
(c) an independence proof, that the question is independent of ZF(C)
(d) a proof that you can't prove "P!=NP" from ZF(C), but which left open the question of whether "P=NP" was provable from ZF(C) or not
(e) proof of something like "P!=NP implies not-CH" or "P!=NP implies not-AC"
I realise the odds are against any of the above. But, here's to hoping for the bizarre unexpected outcome, rather than merely "we just hadn't yet developed the technique to prove what most people thought was true all along" – which would be less profound, less mysterious
On a somewhat different topic, if my hope is for naught, and there indeed exists a proof that "P!=NP" out there waiting to be discovered, even actually discovered in a few years or decades or centuries time, then I've just expressed a counterpossible hope, a hope that an impossible world were actual – which, I think, is a philosophically rather interesting hope to express.
- rsj_hn 5y agoI would prefer option d)
- froh 5y agoHow is n^10^100 polynomial?
- skissane 5y agoO(n^k) is polynomial for all k > 1, and that remains true when k=10^100
- google234123 5y agon^2 is polynomial, 2^n is exponential (variable is in the exponent)
- froh 5y agoDuh. I feel stupid. Thanks for the kind and factual explanation.
- Sharlin 5y ago> (b) a non-constructive proof that P=NP Ouch, that would be so, so frustrating :D
- nightcracker 5y agoSee my other comment, it would also immediately be constructive: https://news.ycombinator.com/item?id=29022963 https://news.ycombinator.com/item?id=29022963
- lisper 5y agoExhibiting an algorithm for any real problem with O(n^k) complexity for k>>1 would be interesting. This is one of the many interesting aspects of this problem. In the real world, for problems people actually care about, k is invariably small, like <<100 and no one knows why. This is one of the many, many vexing aspects of this problem.
- skissane 5y agoWhat about page 4 of [0]: > We remark that, while polynomial, the running time of the algorithm is somewhat abysmal; loose estimates places it somewhere around O(n^(10^100)); the running time of the algorithm of [RT12] is similar. I don’t know if that counts as a “real problem”, and I suppose it is only a “loose estimate” too. [0] https://arxiv.org/pdf/1205.0458v2.pdf https://arxiv.org/pdf/1205.0458v2.pdf
- lisper 5y agoNo, I think that definitely counts as a counterexample. Wow. TIL.
- bawolff 5y agoIntuitively i feel like it makes sense though. The k in O(n^k) roughly corresponds with how many times you loop through the data. Its really hard to imagine a useful algorithm where you need to loop through the data exactly 153 times but then stop there. Either you're going to need to grow the number of loops with input size (be exponential) or surely you got all the data you needed the first 14 times you went through the data. I guess that's not really very rigorus it just feels intuitively right. I just can't imagine a system where you always gain new information regardless of input size on loop iteration 561, but never on iteration 562. Its somewhat similar to how in pure math problems where it seems kind of suspicious if the answer is something like exactly 8.3781 and the problem statement didn't have any related constants in it. Integers are expected, Irrational numbers are expected, decimals with exactly 4 digits sound suspicious.
- orlp 5y agoRegarding (b), a non-constructive proof of P=NP does not exist. Because such a proof is immediately constructive. You can create an enumeration over all Turing machines, and run each of them on the problem, 'diagonally', so we perform one step of computation on machine 1, then 1, 2, 1, 2, 3, 1, 2, 3, 4, etc. This will eventually run each Turing machine for an arbitrary amount of steps. As soon as one of the Turing machines accepts, we also accept. Suppose the nth Turing machine is our poly time machine we have proven to exist (although we don't know n). It takes n steps of our meta algorithm to run this machine 1 step, then n+1 metasteps for the next step and so forth. In total it takes n + n+1 + ... + n+k = O(k^2 + kn) metasteps to run the nth Turing machine k steps. But here's the crux... n does not depend on the input size, only on our problem! Thus it is a constant. In other words, this meta algorithm is quadratically worse (due to k^2 steps) than the optimal algorithm, but it is poly time. Note that the above algorithm doesn't work for co-NP, in which we require that the "no" instances get solved in poly time (in NP we only require the "yes" instances to get solved in poly time).
- dvdkhlng 5y agoIn case anyone wonders, I think the same argument is made in a somewhat easier to understand way in one section of the the P vs NP wikipedia page [2]. But I think that would turn (b) into a special case of (a) i.e. a bizarre algorithm that is completely useless. And it would also be an algorithm of mostly unknown complexity (with P=NP, we'd know it to be ∈ P, but we won't necessarily know anything else). [2] https://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial-time_algorithms https://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial...
- vintermann 5y ago> You can create an enumeration over all Turing machines Wait, can you?
- skissane 5y agoYes. Every possible Turing machine can be defined using a finite number of symbols drawn from a finite alphabet. Each string in a finite alphabet corresponds to an integer, so for every possible Turing machine there is a corresponding integer. There are many conventions for assigning an integer to each Turing machine, but the choice of convention does not matter (so long as it is computable) - the point is, since we can enumerate the integers, and any computable subset thereof, we can enumerate all Turing machines. Note this only applies to standard Turing machines (whether single tape or multi-tape, deterministic or non-deterministic). It does not apply to special types of Turing machines such as oracular Turing machines.
- xcambar 5y agoI'm with you here. The bizarre, unexpected, possibly practically unusable result would be far more interesting than the very much expected P!=NP. Maybe we're spoiled kids of modern TV shows and it shows in our expectations of a good cliffhanger or plot twist in modern science :D
- sacado2 5y agoWhat would be cool, too, would be a proof that yeah, P != NP, sure, but there is an algorithm that can solve any NP-complete problem with a complexity of O((1+Ɛ)^n), with Ɛ very small, so still exponential but solveable in practice in most cases, and we don't know what that algorithm is, we just know it exists.
- whatever1 5y agoI mean the simplex algorithm practically scales linearly for most of our cases, to the point that we assume today Linear Programming a solved problem. We can solve problems with billions of variables and constraints that create a simplex with an astronomical number of vertices. And we can do all these with out of the box solvers. Of course the devil is still there, you can find very small problems that completely break the simplex algorithm.
- rini17 5y agoWould be funny if it came out that all algorithms are P=NP except for vanishignly small subset of cases (which of course is somehow not negligible in practice) and to distinguish them is incomputable :)