I got interested in the mathematical consequences of $P = NP $ after reading this post, Any important consequences with presupposition of P≠NP .

Wang conjectured that if a finite set of Wang tiles can tile the plane, then there exists also a periodic tiling. This conjecture implies the existence of an algorithm to decide whether a given finite set of Wang tiles can tile the plane. However, the algorithmic undecidability of tiling problem implies the existence of Wang tile set that tile the plane only aperiodically.

I am interested in analogous consequences of $P =NP$ to mathematical fields. I am not interested in consequences to computational complexity theory (such as proof complexity). Ideally, if $P=NP$ then certain object must exist with surprising properties. Here are two examples of results from complexity theory (which I am not interested in): If $P=NP$ then there is a sparse NP-complete set (under Karp reduction). Also, if $P=NP$ then there is a short certificate that a graph is not Hamiltonian.

What are the consequences of $P=NP$ to other areas of mathematics?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.