There must be something in information theory to help with proving that to construct a solution to an NP hard problem you need at least that much information.
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.
Ouch, that would be so, so frustrating :D
> 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.
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.
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).
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...
Wait, can you?
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.
In scenario NC, a mathematician devises a highly novel, unexpected and correct proof that P=NP, by finding a way to translate that statement into a statement in some seemingly unrelated area of mathematics, and then using some very deep and profound and innovative techniques to prove that statement in that seemingly unrelated mathematical area. Now, suppose those techniques are fundamentally non-constructive, in that they rely on methods of a kind of which no consistent mathematical constructivist could approve. This kind of proof would not directly turn on finding some novel algorithm for some NP-complete problem and directly proving that the algorithm executes in polynomial time. The only algorithms invoked may be some relatively straightforward algorithms needed to translate P=NP into that very different mathematical area, and then the real genius of the proof may be done in that other area and not explicitly rely on any algorithms at all. This would be a fundamentally non-constructive proof.
By contrast, in scenario C, we have a very different proof that P=NP, which might have as its centrepiece some very novel and obscure and maybe even bizarre algorithm, along with a proof that the algorithm correctly and exactly solves some NP-complete problem, and also a proof that the algorithm executes in polynomial time, and those two proofs may depend on quite subtle details of that specific algorithm. Let us suppose that the profound mathematical genius who devised this algorithm and the associated proofs has great sympathy for mathematical constructivism, and hence does not use in the proof the kinds of techniques of which a mathematical constructivist would disapprove (or, at least, not directly). Maybe even, those proofs are relatively straightforward once you have the algorithm, and coming up with the algorithm was the real genius of the overall proof
Now, you’ve pointed to an example of an already well-known algorithm which solves an NP-complete problem in polynomial time, but only if P=NP. And you are claiming that turns any non-constructive proof into a constructive one. But in scenario NC, our proof was non-constructive in two ways (a) unlike the proof in scenario C, this proof does not have as its centrepiece the construction of a specific example of a novel polynomial time algorithm for solving an NP-complete problem; (b) and unlike the proof in C, it relies on mathematical techniques of which a mathematical constructivist would disapprove. When we combine it with your proposal, it does not alter either of those two ways in which the proof in scenario NC is non-constructive, and so does not actually convert a non-constructive proof into a constructive one as you claim it does.
The term “constructive” has multiple meanings, and even if your argument succeeds in converting a “non-constructive” proof into a “constructive” proof in one sense of “constructive”, it fails to do so in other important senses.
Do you mean "all Turing machines that only accept the 'problem'"?
Because if you literally enumerate over all Turing machines, including trivial ones like those that ignores the input and just acceps/halt no matter what, then it doesn't help you solve the problem at all...
And then the question becomes whether you can enumerate over all Turing machine that accepts only languages of the 'problem'... (or whatever they call it in the standard terminology). I have a feeling this one might not be "computable" regardless of the "input size".
PS: I'm not quite thinking straight now so apologies if I missed something obvious..
I think there is a step which was not explicitly stated in the GP comment. When a given Turing machine accepts, we check whether its output is a valid proof of the answer to our problem. Per definition of NP, we can check that proof in polynomial time. If the check passes, we accept. If the check fails, we ignore that accept and move on.
So we are executing all possible Turing machines in parallel, not just the ones that accept the problem. And when any of them accept, we have to check whether the accept should be ignored or not, because most of the Turing machines are doing something completely unrelated to our problem.
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
Of course the devil is still there, you can find very small problems that completely break the simplex algorithm.
I mean, I agree with the conclusion that P probably doesn’t equal NP, if nothing else because we’ve had an awful lot of very smart people looking at it without any inkling to the contrary. But I don’t generally trust “I don’t see how” intuitions with this sort of thing.
Maybe people who never tried (or thought about) reshelving library books, sorting/delivering mail, etc..
Not sure what you're getting at here. The available useful information is a set of cities each with distances to the other cities. About N^2 pieces of information. A computer can "utilize" all these data in polynomial time.
It is the subtour elimination (remove cycles) that makes the tsp problem difficult. Not the connectivity.
Your arguement suggests the best solution to TSP runs in Θ(n!).
However https://en.m.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm can solve TSP in Θ(2^n n^2)
I did not imply that all information is useful. I proposed that probably there is a lower bound of information that you definitely need to find the optimal solution to the tsp.
Otherwise, we could solve optimal path TSP in polynomial time by binary searching over K.
https://blog.computationalcomplexity.org/2014/01/is-travelin...
Minor difference in wording but a big difference in complexity. Asking for the optimal solution of most of the classic NP problems will make them not NP.
But the linked post also claims checking whether a path is optimal is not in NP. Even then, P=NP would still imply TSP could be solved in polynomial time. So I was kinda wrong, for subtle reasons…
Quantum computing doesn't do what you think it does.
If you take nothing else from this blog: quantum computers won't solve hard problems instantly by just trying all solutions in parallel.”
Are we out of tape already?
That doesn't really even make sense as a sentence. A quantum computer is neither a Turing machine nor a non-deterministic Turing machine.
I guess what you're trying to say is that even if someone proved/disproved BQP=NP it would leave P=NP open.
Explain
If you use the metaphor that superposition is like computing many things in paralell, the problem comes in that when you measure. The superposition collapses to a single answer at random (with probability related to the amplitude of each possibility) which will usually not be the answer you're interested in.
For some problems, people have found ways to extract useful information via classical measurements, e.g. Shor's algorithm (in theory breaking RSA/DSA/ECDSA/DH/ECDH style public-key algorithms [1]). However in the general case this does not work (so AES and hash algorithms are safe for now).
[1] https://en.wikipedia.org/wiki/Wave_function_collapse
[2] https://en.wikipedia.org/wiki/Shor%27s_algorithm#Quantum_par...
Its the question of, "Does a mapping exist from that fast infinite monkey machine to a finite monkey machine that runs in polynomial time?"
I think parent's question is "Can the problem be encoded such that one can prove that no translation can prune the number of monkeys required at an exponential rate?" I have wondered that myself, but never found any particularly useful answer.