7
$\begingroup$

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?

$\endgroup$

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.