Why is the problem of proving the existence or nonexistence of an algorithm that efficiently solves SAT equivalent to $P = NP$, explained simply?

98 Views Asked by At

I am a high school student trying my luck and self-studying topics in mathematics I find interesting. While reading through a course in Math for Computer Science, I came across the statement that deciding whether or not an algorithm to solve the SAT problem in polynomial time exists is equivalent to the $P = NP$ problem. I'm curious about why and the textbook doesn't provide an explanation.

I already know what the P = NP problem, what the SAT problem is and what P, NP, etc. are.

I want, if possible, an explanation of why those two problems are equivalent that a high schooler can understand, with effort.

1

There are 1 best solutions below

2
On BEST ANSWER

First,it is important to realize that “efficiently solves SAT” must be understood as informal shorthand for “Solves SAT in polynomial time”.

If as you say you know what $P$ and $NP$ are, it should be obvious that $P\subseteq NP$. (If not, leave a comment saying so.)

If we could prove $NP\subseteq P$ also, we would know that $P=NP$. To prove $NP\subseteq P$, we would need to show that for any problem $A$ in $NP$, the problem $A$ was also in $P$; that is, for any problem $A$ in $NP$, that there was a polynomial-time algorithm to solve $A$.

SAT is a member of a class of problems called “NP-complete”. These NP-complete problems are in the following sense the ‘hardest’ problems in NP: if any problem in NP is not in P, then problems in NPC are not in P. conversely, if any NP-complete problem is in P, then all of NP is in P.

The reason this is true is that if $A$ is any problem in $NP$, and if $X$ is NP-complete, then an instance of $A$ can be efficiently rewritten (in polynomial time) to be an instance of $X$ whose answer is the same.

Cook's theorem shows how to do this when $X$ is SAT. You can take an instance $A$ of any problem in $NP$, and quickly (in polynomial time) construct a family of statements which can be satisfied if and only if the answer to $A$ was ‘yes’.

So if you could solve SAT instances in polynomial time, you could solve any problem from $NP$ in polynomial time as well, by transforming it into a SAT instance.

Or put more technically, if SAT were in $P$, then every problem in $NP$ would also be in $P$, because any problem in $NP$ can be reduced to SAT. This would prove $NP \subset P$ and therefore (because $P\subseteq NP$ is obvious) $P=NP$.

Conversely, if we somehow already knew $P=NP$, that would imply $NP\subseteq P$, and since SAT is in $NP$, that would prove that SAT was in $P$.

I hope this is at least a little bit helpful.