If language A is Polynomial-Time Reduced to language B (A $\le _p B$) and B ∈ P, what can be concluded about A?
Combining f(x) polynomial computation with B's polynomial solver evaluates x ∈ A in polynomial time, placing A in Class P.
In the Cook-Levin Theorem proof, how is an arbitrary NDTM computation represented as a Boolean Satisfiability (SAT) formula?
Cook and Levin encoded NDTM tableaux (p(n) $\times p(n) grids of computation configurations$) into equivalent CNF boolean formulas.
What is '3-SAT' (3-CNF Satisfiability)?
3-SAT restricts CNF clauses to exactly three literals (e.g. (x1 ∨ ¬x2 ∨ x3) ∧ ...), remaining NP-complete.
Is 2-SAT (CNF formula with at most 2 literals per clause) NP-Complete or in Class P?
2-SAT converts to an implication graph resolved in linear time using Tarjan's SCC algorithm, placing 2-SAT in Class P.
What reduction chain proved 3-SAT to be NP-Complete from SAT?
Karp reduced general CNF clauses (a1 ∨ a2 ∨ ... ∨ ak) to chains of 3-literal clauses using introduced auxiliary variables $y_{i}$.