Understanding Complexity Theory: NP, P vs. NP, PSPACE, and EXP

CMSC 28100 Introduction to Complexity Theory Complexity Theory Spring 2024 Instructor: William Hoza 1

The complexity class NP Let ? be a language Definition:? NP if there exists a randomized polynomial-time Turing machine ? such that for every ? : If ? ?, then Pr ? accepts ? 0 If ? ?, then Pr ? accepts ? = 0 Nondeterministic Polynomial-time 2

How to interpret NP NP is not intended to model the concept of tractability A nondeterministic polynomial-time algorithm is not a practical way to solve a problem Instead, NP is a conceptual tool for reasoning about computation 3

Verification of certificates perspective Let ? be a language Claim:? NPif and only if there exists a deterministic polynomial-time Turing machine ?(a verifier ) and a constant ? such that: For every ? ?, there exists a string ?(a certificate / witness ) such that ? ?? and ? accepts ?,? For every ? ?, for every string ?, the machine ? rejects ?,? 4

NP The P vs. NP problem P P NP It is conjectured that P NP, but nobody knows how to prove it 5

Solving problems in NP by brute force Claim:NP PSPACE Proof: Let ? be a nondeterministic TM that runs in time ??. Given ? ?: 1. For every ? 0,1??, simulate ?, initialized with ? on tape 1 and ? on tape 2 2. If we find some ? such that ? accepts, accept. Otherwise, reject NP can be informally defined as the set of problems that can be solved by brute-force search 6

EXP PSPACE NP P 7

P vs. NP vs. PSPACE vs. EXP P NP PSPACE EXP What we expect: All of these containments are strict What we can prove: At least one of these containments is strict. (Why?) 8

Complexity of CLIQUE Recall: CLIQUE = { ?,? ? has a ?-clique} Last time, we discussed the fact that CLIQUE NP Consequence: If P = NP, then CLIQUE P Plan for this week: We will prove that if P NP, then CLIQUE P This will provide evidence that CLIQUE P To prove it, we will use concepts of NP-hardness and NP-completeness 9

NP-hardness Definition: Let ? be a language. Suppose that for every ? NP, there is a poly-time mapping reduction from ? to ?. In this case, we say that ? is NP-hard ? is NP-hard means ? is at least as hard as every language in NP 10

NP-completeness Definition: Let ? be a language. We say that ? is NP-complete if ? is NP-hard and ? NP The NP-complete languages are the hardest languages in NP If ? is NP-complete, then the language ?can be said to capture / express the entire complexity class NP 11

NP-complete languages are probably not in P Claim: Suppose ? is NP-complete. Then ? P if and only if P = NP Proof: First, assume P = NP. Since ? NP, it follows that ? P Now assume P NP, i.e., there is some language ?HARD NP P By NP-hardness, there is a poly-time mapping reduction from ?HARD to ? Since ?HARD P, this implies ? P 12

NP-completeness NP-hard NP-complete NP P 13

Proving NP-completeness How can we prove that a language like CLIQUE is NP-complete? How can we use graph theory to simulate Turing machines? Key idea: Code as Data 14

Code as data, revisited Recall principle: A Turing machine ? can be encoded as a string ? ? is an algorithm, but at the same time, ? can be an input to another algorithm! Similar idea: A circuit ? can be encoded as a string ? You investigated ways to do this on problem set 5 ?is an algorithm, but at the same time, ? can be an input to another algorithm! What can we do with this idea? 15

Circuit value problem Let CIRCUIT-VALUE = { ?,? ? is a circuit and ? ? = 1} Claim:CIRCUIT-VALUE P Proof sketch: Suppose ? has ? nodes. To compute ? ? : 1) Mark all the input nodes with their values 2) While there is an unmarked node: For every gate ?, find all the nodes that feed into ?. If they are all marked with their a) values, then mark ? with its value 16

Let ? be an input to ?. How should ? be interpreted? Constructing circuits that implement TMs A:? is the description of a circuit that decides ? B:? is the description of a Turing machine that decides ? Let ? P where ? C:? is the binary encoding of a string in ? D:? is the binary encoding of a string in ? Since P PSIZE, we know that for every ?, there exists a polynomial-size Respond at PollEv.com/whoza or text whoza to 22333 circuit that computes ??, i.e., it decides ? on inputs of length ? Theorem: There is a polynomial-time algorithm such that given 1?, the algorithm outputs the description ? of a circuit ? that computes ?? Proof sketch: Use the circuit construction we used to prove P PSIZE 17

Circuit satisfiability Satisfiable Let ? be an ?-input 1-output circuit ?1 ?2 We say that ? is satisfiable if there exists ? {0,1}? such that ? ? = 1 Unsatisfiable ?1 ?2 18

Circuit satisfiability is NP-complete Let CIRCUIT-SAT = { ? ? is a satisfiable circuit} Theorem: CIRCUIT-SAT is NP-complete. Consequence: Studying CIRCUIT-SAT (one specific language) is equivalent to studying the abstract concept of verifiability (as modeled by the complexity class NP) 19

Proof that CIRCUIT-SAT NP Given ? , where ? is an ?-input 1-output circuit: Pick ? 0,1? at random 1. Check whether ? ? = 1 (recall CIRCUIT-VALUE P) 2. Accept if ? ? = 1; reject if ? ? = 0 3. 20

Proof that CIRCUIT-SAT is NP-hard Let ? be any language in NP Our job: Design a mapping reduction from ? to CIRCUIT-SAT 21