BobDole12345
2017-08-18, 12:54 AM
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.
https://arxiv.org/abs/1708.03486
Why is this important? To put it short, if it were the case that P = NP were true, we could solve extremely hard problems very quickly. This has drastic consequences, say, if applied to protein folding, a cure to cancer could be discovered. The paper has yet to be peer reviewed.
https://arxiv.org/abs/1708.03486
Why is this important? To put it short, if it were the case that P = NP were true, we could solve extremely hard problems very quickly. This has drastic consequences, say, if applied to protein folding, a cure to cancer could be discovered. The paper has yet to be peer reviewed.