Tag Archives: np problem

A Solution of the P versus NP Problem

Posted on by

Berg and Ulfberg and Amano and Maruoka have used CNF-DNF-approximators to prove exponential lower bounds for the monotone network complexity of the clique function and of Andreev’s function. We show that these approximators can be used to prove the same lower bound for their non-monotone network complexity. This implies P not equal NP.

Source: [1708.03486] A Solution of the P versus NP Problem

More background at:  The P-versus-NP page

This page collects links around papers that try to settle the “P versus NP” question (in either way). Here are some links that explain/discuss this question:

The Mathematical Trick That Helped Smash The Record For The Largest Number Ever Factorised By A…

Posted on by

And in any case, because this trick works using only 4 qubits, it can easily be reproduced on any classical computer. So it’s not so useful after all.

via The Mathematical Trick That Helped Smash The Record For The Largest Number Ever Factorised By A… — The Physics arXiv Blog — Medium.

Here’s a paper on this subject:

[1411.6758] Quantum factorization of 56153 with only 4 qubits.