Editing Boolean satisfiability problem (section)

==Finding a satisfying assignment==
While SAT is a [[decision problem]], the [[search problem]] of finding a satisfying assignment reduces to SAT. That is, each algorithm which correctly answers whether an instance of SAT is solvable can be used to find a satisfying assignment. First, the question is asked on the given formula Φ. If the answer is "no", the formula is unsatisfiable. Otherwise, the question is asked on the partly instantiated formula Φ[[substitution (logic)|{''x''<sub>1</sub>=TRUE}]], that is, Φ with the first variable ''x''<sub>1</sub> replaced by TRUE, and simplified accordingly. If the answer is "yes", then ''x''<sub>1</sub>=TRUE, otherwise ''x''<sub>1</sub>=FALSE. Values of other variables can be found subsequently in the same way. In total, ''n''+1 runs of the algorithm are required, where ''n'' is the number of distinct variables in Φ.

This property is used in several theorems in complexity theory:

* [[NP (complexity)|NP]] ⊆ [[P/poly]] ⇒ [[PH (complexity)|PH]] = [[Polynomial hierarchy#Definitions|Σ<sub>2</sub>]] ([[Karp–Lipton theorem]])
* [[NP (complexity)|NP]] ⊆ [[BPP (complexity)|BPP]] ⇒ [[NP (complexity)|NP]] = [[RP (complexity)|RP]]
* [[P (complexity)|P]] = [[NP (complexity)|NP]] ⇒ [[FP (complexity)|FP]] = [[FNP (complexity)|FNP]]