# NP-Complete problem The hardest problem in NP is the SAT problem as any problem in NP can be solved efficiently if there is an efficient solution to SAT: model the problem as UTM and ask if there is an instance that is accepted by it. A problem that belonging [[NP problem|NP]] class and SAT (any problem that is already reducible from SAT) can be reduced to it (solving it will solve SAT) - is NP-complete. we have $Problem < SAT$ As an NP-complete problem is in NP, it can be modeled by UTM and therefore can be efficiently solved by SAT problem (The hardest problem in NP).$Problem > SAT$ . This makes the problem equivalent in hardness to SAT or any other problem which belong to NP-complete. ## Theorem: $\text{NP-Complete}$ problem class is not empty. Theorem: $\text{SAT}\in \text{NP-Complete}$ Proof (sketch): Given a solution for SAT one substitute variables as in the proposed solution, evaluate the boolean formula and verify if the result is TRUE or FALSE. This can be done in linear time and so is efficient i.e., $\text{SAT}\in \text{NP}$. In [[NP hard problem]] note, we "showed" that $\text{SAT}\in \text{NP-hard}$. Combining the results, we get $\text{SAT}\in \text{NP-Complete}$ $\square$ ## Created 2023-04-23 13:26