The 50-year-old P-NP problem that eludes theoretical computer science
technologyreview.com
technologyreview.com
(If you can verify any proof using Isabelle or Coq PM me.)
Rofl. Yep, if i write a machine checkable proof of the most famous open problem in all of computer science, that's definitely the first thing i'll do.
If it was n^10, well, likely different story, involving three letter agencies, I’m afraid.
yeah, but in my case (and presumably the previous commenter's case) I don't know who Zaik on HN is and if they are recognizable in the field. That they asked increases my feeling that it is likely they are recognizable but surely anyone who solves p!=np isn't going to just follow something as irrational as a feeling.
Edit: I now noticed that a few of them have:
3.[Equal]:... Zhu Daming, Luan Junfeng and M. A. Shaohan (all affiliated with Shandong University, China) refute these claims in their paper "Hardness and methods to solve CLIQUE" (Journal of Computer Science and Technology 16, 2001, pp 388-391).
Sadly, no. I have talked to the author of one of those papers and apparently there is not a lot of motivation to check new proof attempts from the relevant people anymore.
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.
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...
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.
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.
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
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.
> 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.
Of course the devil is still there, you can find very small problems that completely break the simplex algorithm.
Ouch, that would be so, so frustrating :D
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…
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.
Explain
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...
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.
Quantum computing doesn't do what you think it does.
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.
If you take nothing else from this blog: quantum computers won't solve hard problems instantly by just trying all solutions in parallel.”
I hate that P is often understood as "easily solvable". There's problems inside P that require O(n^A) time algorithms, where A is some scaringly large ackerman number. And that just barely scratches the surface of P. There are other, unimaginably harder, problems in P.
It is very arrogant for us to say that P<NP, when we still know so little about P.
I'm rooting for P=NP, even if this only serves to explore harder problems inside P, with terrifyingly slow algorithms.
There are so much we don’t know about how space & time complexities commune
The weird thing is that GPT3 Codex can perhaps be used to solve some (space-constrainted) subsets of problems that are combinatorial weird. Maybe by pouring all these training data to it it is approximating some unimaginable algo in P that we have no knowledge about
Will be wild if there is some (time-space) correspondence; NPSPACE = PSPACE Implies NP = P would be interesting
Sort of like Fermat’s Last Theorem: the proof is out there.
There is likely an island of consistent axiomatic logical statements that we must not only wait for someone to reach by happenstance, but to decipher and know what to do with them. According to Fermat, his proof was omitted due to lack of space in the margin. I suppose it's good to let others share in the glory now and again, if on centuries-delay.
If there exists an algorithm that always guesses correctly then we can solve NP problems?
That's just the definition of NP restated. One of the definitions of NP is all the problems that can be solved in polynomial time if at every choice we had a method of always guessing correctly.
The question of NP=P is if such a method can actually be implemented in polynomial time on a Turing machine.
So yes, you are correct, it stands to reason that if NP=P, then NP=P.
If you believe really so strongly that P!=NP without actual proof, you're actually just making a guess, and then saying you can make good guesses. But the process of doing so implies you actually believe P=NP.
So seems like the majority opinion but not universal.
> The million-dollar question posed by P vs. NP is this: Are these two classes of problems one and the same? Which is to say, could the problems that seem so difficult in fact be solved with an algorithm in a reasonable amount of time, if only the right, devilishly fast algorithm could be found? If so, many hard problems are suddenly solvable. And their algorithmic solutions could bring about societal changes of utopian proportions—in medicine and engineering and economics, biology and ecology, neuroscience and social science, industry, the arts, even politics and beyond.
Okay, I'd like to have a list of such problems! Yes, some of them are 'intractable', but not all.
But we are not attacking the problems that are solvable easily enough now and that would
"bring about societal changes of utopian proportions—in medicine and engineering".
We are not solving such problems because too few of them exist, that is, mostly the problems don't exist.
Here's what we can do now and have been able to do easily enough for decades:
The challenge of P versus NP is for (1) exactly optimal (for optimization problems) solutions to (2) worst case problems in (3) polynomial time.
But if we will settle for 99+% of the savings of optimal solutions for problems that are not worst case but still constitute nearly all the practical problems in reality, then usually we can do well.
E.g., 0-1 integer linear programming problems are in NP-complete. The last such problem I attacked had 40,000 constraints and 600,000 variables. I found a feasible solution within 0.025% of optimality in 900 seconds on a single processor computer using ordinary linear programming and some non-linear duality theory.
Blunt, practical fact: In practice, there just are not many practical NP complete optimization problems that people want solved. For practical NP-complete optimization problems, we can usually do well, save nearly all the money to be saved with an optimal solution, for reasonable effort, but, in practice, we don't do that very often because there are not many people with such problems who want such solutions -- for the savings, they just don't care enough even to pick up a phone.
The claim that an algorithm that shows that P = NP would
"bring about societal changes of utopian proportions—in medicine and engineering ..."
is just not true -- the economy does not have many such problems. If the problems were there, then people would be successfully attacking those problems now; the "utopian proportions" would create some recruiting. But the recruiting is not there. Over decades sending many hundreds of resume copies showing such problem solving abilities yields no responses. A person good at such optimization faces deep and profound unemployment -- they just CANNOT be hired, at any price, are just NOT wanted. Quite literally, they would have a better career, e.g., make more money, with a simple, ordinary grass mowing service -- no joke or exaggeration.
For the problem with 40,000 constraints and 600,000 variables, I got that via email from two guys, a CEO and his buddy. The buddy had tried simulated annealing, run for days, and quit without knowing how close the results were to optimality. Getting the problem via email, in two weeks I did the non-linear duality derivations and wrote and ran the software, for free. Via email I sent the news of success back to the CEO. He was totally not interested: My success would have embarrassed his buddy, and that meant that my work was not wanted, even for $1. Blunt fact: Not many people have any interest at all, and of those nearly all have very little interest.
Point: The claim
"bring about societal changes of utopian proportions—in medicine and engineering ..."
is nonsense because the needed people with the problems are far too few.
A useful NP problem is generating code to meet some requirements. Instead of programming, you can write just some tests and get some code that passes them. Deep learning is a computationally feasible way of automatically finding a function that approximately matches some data points, but it doesn't always generalize well. Searching for the shortest program that matches all the data points should generalize better.