CSC373
Weeks 7 & 8: Complexity
373F20 – Nisarg Shah 1
Recap
• Linear Programming ➢ Standard formulation
➢ Slack formulation
➢ Simplex
➢ Duality
➢ Formulating given problems as LPs
373F20 – Nisarg Shah 2
This & Next Week
• Applications of linear programming ➢ Shortest path
➢ Network flow
• A note about integer programming
• Complexity
➢ Turing machines, computability, efficient computation
➢ P, NP, and NP-completeness
➢ Reductions
➢ Idea behind NP-completeness of SAT and 3SAT ➢ NP vs co-NP
➢ Other complexity classes
373F20 – Nisarg Shah 3
Network Flow via LP
• Problem
➢ Input: directed graph 𝐺 = (𝑉, 𝐸), edge capacities
𝑐: 𝐸 → R≥0
➢ Output: Value 𝑣 𝑓∗ of a maximum flow 𝑓∗
• Flow 𝑓 is valid if:
➢ Capacity constraints: ∀ 𝑢,𝑣 ∈ 𝐸:0 ≤ 𝑓 𝑢,𝑣 ≤ 𝑐(𝑢,𝑣) ➢ Flow conservation: ∀𝑢:σ 𝑢,𝑣 ∈𝐸 𝑓 𝑢,𝑣 = σ 𝑣,𝑢 ∈𝐸 𝑓 𝑣,𝑢
• Maximize𝑣 𝑓 =σ𝑠,𝑣 ∈𝐸𝑓 𝑠,𝑣
Linear constraints Linear objective!
373F20 – Nisarg Shah 4
Network Flow via LP
maximize
𝑓 𝑠𝑣
(𝑠,𝑣)∈𝐸
0≤𝑓 ≤𝑐𝑢,𝑣
𝑢𝑣 for all (𝑢,𝑣) ∈ 𝐸
𝑓=𝑓 𝑢𝑣 𝑣,𝑤
for all 𝑣 ∈ 𝑉\{𝑠, 𝑡}
(𝑢,𝑣)∈𝐸
(𝑣,𝑤)∈𝐸
Exercise: Write the dual of this LP. What is the dual trying to find?
373F20 – Nisarg Shah 5
Shortest Path via LP
• Problem
➢ Input: directed graph 𝐺 = 𝑉, 𝐸 , edge weights
𝑤: 𝐸 → R≥0, source vertex 𝑠, target vertex 𝑡
➢ Output: weight of the shortest-weight path from 𝑠 to 𝑡
• Variables: for each vertex 𝑣, we have variable 𝑑𝑣 Why max?
If objective was min., then we could set all variables 𝑑𝑣 to 0.
Exercise: prove formally that this works!
373F20 – Nisarg Shah 6
But…but…
• For these problems, we have different combinatorial algorithms that are much faster and run in strongly polynomial time
• Why would we use LP?
• For some problems, we don’t have faster algorithms than solving them via LP
373F20 – Nisarg Shah 7
Multicommodity-Flow
• Problem:
➢ Input: directed graph 𝐺 = (𝑉, 𝐸), edge capacities 𝑐: 𝐸 → R≥0,
𝑘 commodities (𝑠𝑖 , 𝑡𝑖 , 𝑑𝑖 ), where 𝑠𝑖 is source of commodity 𝑖, 𝑡𝑖 is sink, and 𝑑𝑖 is demand.
➢ Output: valid multicommodity flow 𝑓 , 𝑓 , … , 𝑓 , where 𝑓 has value 12𝑘𝑖
𝑑 and all 𝑓 jointly satisfy the constraints 𝑖𝑖
The only known polynomial time algorithm for this problem is based on solving LP!
373F20 – Nisarg Shah 8
Integer Linear Programming
• Variable values are restricted to be integers
• Example:
➢ Input: 𝑐 ∈ R𝑛, 𝑏 ∈ R𝑚, 𝐴 ∈ R𝑚×𝑛 ➢ Goal:
Maximize Subject to
• Does this make the problem easier or harder? ➢ Harder. We’ll prove that this is “NP-complete”.
𝑐𝑇𝑥 𝐴𝑥 ≤ 𝑏
𝒙 ∈ {𝟎, 𝟏}𝒏
373F20 – Nisarg Shah 9
LPs are everywhere…
➢ Microeconomics
➢ Manufacturing
➢ VLSI (very large scale integration) design
➢ Logistics/transportation
➢ Portfolio optimization
➢ Bioengineering (flux balance analysis)
➢ Operations research more broadly: maximize profits or minimize costs, use linear models for simplicity
➢ Design of approximation algorithms
➢ Proving theorems, as a proof technique ➢…
373F20 – Nisarg Shah 10
Introduction to Complexity
• You have a problem at hand
• You try every technique known to humankind for finding a
polynomial time algorithm, but fail.
• You try every technique known to humankind for proving that there cannot exist a polynomial time algorithm for your problem, but fail.
• What do you do?
➢ Prove that it is NP-complete, of course!
373F20 – Nisarg Shah 11
Turing Machines
• “Which problems can a computer (not) solve in a certain amount of time?”
➢ How do we mathematically define what a computer is?
• Alan Turing (“Father of Computer Science”), 1936
➢ Introduced a mathematical model
➢ “Turing machine”
➢ All present-day computers can be simulated by a Turing machine ➢ Fun fact: So can all the quantum computers
o But TM might take longer to solve the same problem
373F20 – Nisarg Shah 12
Turing Machines
• We won’t formally introduce…but at a high level…
• Turing machine ➢ Tape
o Input is given on tape
o Intermediate computations can be written there o Output must to be written there
➢ Head pointer
o Initially pointing at start of input on tape
➢ Maintains an internal “state”
➢ A transition function describes how to change state, move head pointer, and read/write symbols on tape
373F20 – Nisarg Shah 13
Computability
• Church-Turing Thesis
➢ “Everything that is computable can be computed by a Turing
machine”
➢ Widely accepted, cannot be “proven”
➢ There are problems which a Turing machine cannot solve, regardless of the amount of time available
o E.g., the halting problem
• What about the problems we can solve? How do we define the time required?
➢ Need to define an encoding of the input and output
373F20 – Nisarg Shah 14
Encoding
• What can we write on the tape?
➢ 𝑆 = a set of finite symbols
𝑆 set of all finite strings using symbols from = 𝑛𝑆 0≥𝑛ڂ = ∗𝑆 ➢
• Input: 𝑤 ∈ 𝑆∗
➢ Length of input = |𝑤| = length of 𝑤 on tape
• Output:𝑓 𝑤 ∈𝑆∗
➢ Length of output = 𝑓 𝑤
➢ Decision problems: output = “YES” or “NO”
o E.g. “does there exist a flow of value at least 7 in this network?”
373F20 – Nisarg Shah 15

Encoding
• Example:
➢ “Given 𝑎 , 𝑎 , … , 𝑎 , compute σ𝑛 𝑎
”
o Suppose we are told that 𝑎𝑖 ≤ 𝐶 for all 𝑖
12𝑛 𝑖=1𝑖
➢ What |𝑆| should we use?
o 𝑆 = {0,1} ( 𝑆 = 2, binary representation)
• Lengthofinput=𝑂 log2𝑎1 +⋯+log2𝑎𝑛
o What about 3-ary ( 𝑆 = 3) or 18-ary ( 𝑆 = 18)?
=𝑂 𝑛log2𝐶
• Only changes the length by a constant factor, still 𝑂(𝑛 log 𝐶)
oWhataboutunary(conceptually, 𝑆 =1)? • Length blows up exponentially to 𝑂 𝑛𝐶
o Binary is already good enough, but unary isn’t
373F20 – Nisarg Shah 16
Efficient Computability
• Polynomial-time computability
➢ A TM solves a problem in polynomial time if there is a polynomial 𝑝 such that on every instance of 𝑛-bit input and 𝑚-bit output, the TM halts in at most 𝑝(𝑛, 𝑚) steps
➢ Polynomial: 𝑛, 𝑛2, 5𝑛100 + 1000𝑛3, 𝑛 log100 𝑛 = 𝑜 𝑛1.001
➢ Non-polynomial: 2𝑛, 2 𝑛, 2log2 𝑛
• Extended Church-Turing Hypothesis 𝑛
If you ask the Turing machine to write a 2 -bit output, it’s only reasonable
➢ “Everything that is efficiently computable is computable by a TM in
to let it take 2𝑛 time…but usually, we’ll look at problems where output is
polynomial time”
➢ But in this course, efficient = polynomial-time
O(length of input), so we can ignore this 𝑚 ➢ Much less widely accepted, especially today
373F20 – Nisarg Shah 17
P
• P (polynomial time)
➢ The class of all decision problems computable by a TM in polynomial
time
• Examples
➢ Addition, multiplication, square root
➢ Shortest paths
➢ Network flow
➢ Fast Fourier transform
➢ Checking if a given number is a prime [Agrawal-Kayal-Saxena 2002]
➢…
373F20 – Nisarg Shah 18
NP
• NP (nondeterministic polynomial time) intuition ➢ Subset sum problem:
Given an array {−7, −3, −2, 5, 8}, is there a zero-sum subset?
➢ Enumerating all subsets is exponential
➢ But…given {-3, -2, 5}, we can verify in polynomial time that it is indeed a valid subset and has zero sum
➢ A nondeterministic Turing machine could “guess” the solution and then test if it has zero sum in polynomial time
373F20 – Nisarg Shah 19
NP
• NP (nondeterministic polynomial time)
➢ The class of all decision problems for which a YES answer can be verified by a TM in polynomial time given polynomial length “advice” or “witness”.
➢ There is a polynomial-time verifier TM 𝑉 and another polynomial 𝑝 such that
o For all YES inputs 𝑥, there exists advice 𝑦 with 𝑦 = 𝑝 𝑥 on which 𝑉(𝑥, 𝑦) returns YES
o For all NO inputs 𝑥, 𝑉(𝑥, 𝑦) returns NO for every possible 𝑦
➢ Informally: “Whenever the answer is YES, there’s a short proof of it.” o When the answer is NO, there may not be any short proof for it.
373F20 – Nisarg Shah 20
co-NP
• co-NP
➢ Same as NP, except whenever the answer is NO, there is a short
proof of it
• Open questions ➢ NP = co-NP?
➢ P = NP ∩ co-NP?
➢ And…drum roll please…
𝑃 = 𝑁𝑃?
373F20 – Nisarg Shah 21
P versus NP
• Lance Fortnow in his article on P and NP in Communications of the ACM, Sept 2009
“The P versus NP problem has gone from an interesting problem related to logic to perhaps the most fundamental and important mathematical question of our time, whose importance only grows as computers become more powerful and widespread.”
373F20 – Nisarg Shah 22
Millenium Problems
• Award of $1M for each problem by the Clay Math institute
1. Birch and Swinnerton-Dyer Conjecture
2. Hodge Conjecture
3. Navier-Stokes Equations
4. P = NP?
5. Poincare Conjecture (Solved)1
6. Riemann Hypothesis
7. Yang-Mills Theory
Claim: Worth >> $1M
1Solved by Grigori Perelman (2003): Prize unclaimed
373F20 – Nisarg Shah 23
Cook’s Conjecture
• Cook’s conjecture
➢ (And every sane person’s belief…) ➢ 𝑃 is likely not equal to 𝑁𝑃
• Why do we believe this?
➢ There is a large class of problems (NP-complete)
➢ By now, contains thousands and thousands of problems
➢ Each problem is the “hardest problem in NP”
➢ If you can efficiently solve any one of them, you can efficiently solve every problem in NP
o Despite decades of effort, no polynomial time solution has been found for any of them
373F20 – Nisarg Shah 24
Reductions
• Problem 𝐴 is p-reducible to problem 𝐵 (denoted 𝐴 ≤𝑝 𝐵) if an “oracle” (subroutine) for 𝐵 can be used to efficiently solve 𝐴
➢ You can solve 𝐴 by making polynomially many calls to the oracle and doing additional polynomial-time computation
• Question: If 𝐴 is p-reducible to 𝐵, then which of the following is true?
a) If 𝐴 cannot be solved efficiently, then neither can 𝐵.
b) If 𝐵 cannot be solved efficiently, then neither can 𝐴.
c) Both. d) None.
373F20 – Nisarg Shah 25
Reductions
• Problem 𝐴 is p-reducible to problem 𝐵 (denoted 𝐴 ≤𝑝 𝐵) if an “oracle” (subroutine) for 𝐵 can be used to efficiently solve 𝐴
➢ You can solve 𝐴 by making polynomially many calls to the oracle and doing additional polynomial computation
• Question: If I want to prove that my problem 𝑋 is “hard”, I should:
a) Reduce my problem 𝑋 to a known hard problem.
b) Reduce a known hard problem to my problem 𝑋.
c) Both. d) None.
373F20 – Nisarg Shah 26
NP-completeness
• NP-completeness
➢ A problem 𝐵 is NP-complete if it is in NP and every problem 𝐴 in NP
is p-reducible to 𝐵
➢ Hardest problems in NP
➢ If one of them can be solved efficiently, every problem in NP can be solved efficiently, implying P=NP
• Observation:
➢ If 𝐴 is in NP, and some NP-complete problem 𝐵 is p-reducible to 𝐴,
then 𝐴 is NP-complete too
o “If I could solve A, then I could solve B, and then I could solve any problem in NP”
373F20 – Nisarg Shah 27
NP-completeness
• But this uses an already known NP-complete problem to prove another problem is NP-complete
• How do we find the first NP-complete problem?
➢ How do we know there are any NP-complete problems at all? ➢ Key result by Cook
➢ First NP-complete problem: SAT
o By a reduction from an arbitrary problem in NP to SAT o “From first principles”
373F20 – Nisarg Shah 28
CNF Formulas
• Conjunctive normal form (CNF) ➢ Boolean variables 𝑥1, 𝑥2, … , 𝑥𝑛
➢ Their negations 𝑥ҧ1, 𝑥ҧ2, … , 𝑥ҧ𝑛
➢ Literal l: a variable or its negation
➢ Clause 𝐶 = l1 ∨ l2 ∨ ⋯ ∨ l𝑟 is a disjunction of literals
➢ CNF formula 𝜑 = 𝐶 ∧ 𝐶 ∧ ⋯ ∧ 𝐶 is a conjunction of clauses 12𝑚
o 𝑘CNF: Each clause has at most 𝑘 literals
• We’ll abuse notation a little and assume there are exactly 𝑘 • Example of 3CNF
𝜑= 𝑥ҧ1 ∨𝑥2 ∨𝑥3 ∧ 𝑥1 ∨𝑥ҧ2 ∨𝑥3 ∧ 𝑥ҧ1 ∨𝑥2 ∨𝑥4 ∧(𝑥ҧ3 ∨𝑥ҧ4 ∨𝑥1)
373F20 – Nisarg Shah 29
SAT and 3SAT
• Example of 3CNF
𝜑= 𝑥ҧ1 ∨𝑥2 ∨𝑥3 ∧ 𝑥1 ∨𝑥ҧ2 ∨𝑥3 ∧ 𝑥ҧ1 ∨𝑥2 ∨𝑥4 ∧(𝑥ҧ3 ∨𝑥ҧ4 ∨𝑥1)
• “SAT” (Satisfiability) Problem:
➢ A CNF formula 𝜑 is satisfiable if there is an assignment of truth values (TRUE/FALSE) to variables under which the formula evaluates to TRUE
o That means, in each clause, at least one literal is TRUE ➢ SAT: “Given a CNF formula 𝜑, is it satisfiable?”
➢ 3SAT: “Given a 3CNF formula 𝜑, is it satisfiable?”
373F20 – Nisarg Shah 30
SAT and 3SAT
• Cook-Levin Theorem
➢ SAT (and even 3SAT) is NP-complete
• Doesn’t use any known NP-complete problem ➢ Directly reduces any given NP problem to SAT
➢ Reduction is a bit complex, so we’ll defer it until later
➢ But for now, let’s assume SAT and 3SAT are NP-complete and reduce them to other problems (and then those problems to other problems…)
373F20 – Nisarg Shah 31
NP-Complete Examples
• NP-complete problems
➢ SAT = first NP complete problem
➢ Decision TSP: Is there a route visiting all 𝑛 cities with total distance at most 𝑘?
➢ 3-Colorabitility: Can the vertices of a graph be colored with at most 3 colors such that no two adjacent vertices have the same color?
➢ Karp’s 21 NP-complete problems
• co-NP-complete
➢ Tautology problem (“negation” of SAT):
o “Given a CNF formula 𝜑, does it always evaluate to TRUE regardless of variable assignments?”
373F20 – Nisarg Shah 32
Complexity
By Behnam Esfahbod, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=3532181
373F20 – Nisarg Shah 33
⋮⋮
373F20 – Nisarg Shah 34
373F20 – Nisarg Shah 35
Just A Tad Bit of History
• [Cook 1971]
➢ Proved 3SAT is NP-complete in seminal paper
• [Karp 1972]
➢ Showed that 20 other problems are also NP-complete ➢ “Karp’s 21 NP-complete problems”
➢ Renewed interest in this idea
• 1982: Cook won the Turing award
373F20 – Nisarg Shah 36
Independent Set
• Problem
➢ Input: Undirected graph 𝐺 = (𝑉, 𝐸), integer 𝑘
➢ Question: Does there exist a subset of vertices 𝑆 ⊆ 𝑉 with 𝑆 = 𝑘 such that for each edge, at most one of its endpoints is in 𝑆?
Example:
• Does this graph have an independent set of size 6?
• Yes!
• Does this graph have an
independent set of size 7? • No!
= independent set
373F20 – Nisarg Shah 37
Independent Set
• Claim: Independent Set is in NP
➢ Recall: We need to show that there is a polynomial-time algorithm
which
o Can accept every YES instance with the right polynomial-size advice o Will not accept a NO instance with any advice
➢ Advice: the actual independent set 𝑆 ➢Algorithm:checkif𝑆isanindependentsetandif 𝑆 =𝑘 ➢ Simple!
373F20 – Nisarg Shah 38
Independent Set
• Claim: 3SAT ≤𝑝 Independent Set
➢ Given a formula 𝜑 of 3SAT with 𝑘 clauses, construct an instance (𝐺, 𝑘)
of Independent Set as follows
o Create 3 vertices for each clause (one for each literal)
o Connect them in a triangle
o Connect the vertex of each literal to each of its negations
373F20 – Nisarg Shah 39
Independent Set
➢ Why does this work?
o 3SAT = YES ⇒ Independent Set = YES
• From each clause, take any literal that is TRUE in the assignment o Independent Set = YES ⇒ 3SAT = YES
• Independent set 𝑆 must contain one vertex from each triangle
• No literal and its negation are both in 𝑆
• Set literals in 𝑆 to TRUE, their negations to FALSE, and the rest to arbitrary values
373F20 – Nisarg Shah 40
Different Types of Reductions
•𝐴≤𝐵
➢ Karp reductions
o Take an arbitrary instance of 𝐴, and in polynomial time, construct a single instance of 𝐵 with the same answer
o Very restricted type of reduction
o The reduction we just constructed was a Karp reduction
➢ Turing/Cook reductions
o Take an arbitrary instance of 𝐴, and solve it by making polynomially many calls to an oracle for solving 𝐵 and some polynomial-time extra computation
o Very general reduction
o In this course, we’ll allow Turing/Cook reductions, but whenever possible, see if you can construct a Karp reduction
373F20 – Nisarg Shah 41
Subset Sum
• Problem
➢ Input: Set of integers 𝑆 = {𝑤 ,…,𝑤 }, integer 𝑊
1𝑛
➢ Question: Is there 𝑆′ ⊆ 𝑆 that adds up to exactly 𝑊?
• Example
➢ 𝑆 = {1, 4, 16, 64, 256, 1040, 1041, 1093, 1284, 1344}, 𝑊 = 3754? ➢ Yes!
o 1 + 16 + 64 + 256 + 1040 + 1093 + 1284 = 3754
373F20 – Nisarg Shah 42
Subset Sum
• Claim: Subset Sum is in NP
➢ Recall: We need to show that there is a polynomial-time algorithm
which
o Can accept every YES instance with the right polynomial-size advice o Will not accept a NO instance with any advice
➢ Advice: the actual subset 𝑆′
➢ Algorithm: check that 𝑆′ is indeed a subset of 𝑆 and sums to 𝑊 ➢ Simple!
373F20 – Nisarg Shah 43
Subset Sum
• Claim: 3SAT ≤𝑝 Subset Sum
➢ Given a formula 𝜑 of 3SAT, we want to construct (𝑆, 𝑊) of Subset Sum
with the same answer
➢ In the table in the following slide:
o Columns are for variables and clauses
o Each row is a number in 𝑆, represented in decimal
o Number for literal l : has 1 in its variable column and in the column of every clause where that literal appears
• Number selected = literal set to TRUE
o “Dummy” rows: can help make the sum in a clause column 4 if and only if at least one literal is set to TRUE
373F20 – Nisarg Shah 44
Subset Sum
• Claim: 3SAT ≤𝑝 Subset Sum
Decimal representation
373F20 – Nisarg Shah 45
Subset Sum
• Note
➢ The Subset Sum instance we constructed has “large” numbers
o Their values are exponentially large (~10#𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒𝑠+#𝑐𝑙𝑎𝑢𝑠𝑒𝑠) o But the number of bits required to write them is polynomial
➢ Can we hope to construct Subset Sum instance with numbers whose values are only 𝑝𝑜𝑙𝑦(#𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒𝑠, #𝑐𝑙𝑎𝑠𝑢𝑠𝑒𝑠) large?
o Unlikely, as that would prove 𝑃 = 𝑁𝑃!
o Like Knapsack, Subset Sum can be solved in pseudo-polynomial time
• That is, in polynomial time if the numbers are only polynomially large in value
373F20 – Nisarg Shah 46
3-Coloring
• Problem
➢ Input: Undirected graph 𝐺 = (𝑉, 𝐸)
➢ Question: Can we color each vertex of 𝐺 using at most three colors such that no two adjacent vertices have the same color?
373F20 – Nisarg Shah 47
3-Coloring
• Claim: 3-coloring is in NP
➢ Recall: We need to show that there is a polynomial-time algorithm
which
o Can accept every YES instance with the right polynomial-size advice o Will not accept a NO instance with any advice
➢ Advice: colors of the nodes in a valid 3-coloring ➢ Algorithm: check that this is a valid 3-coloring ➢ Simple!
373F20 – Nisarg Shah 48
3-Coloring
• Claim: 3SAT ≤𝑝 3-Coloring
➢ Given a 3SAT formula 𝜑, we want to construct a graph 𝐺 such that 𝐺 is
3-colorable if and only if 𝜑 has a satisfying assignment ➢ 𝐺 will have the following nodes:
o Type 1: true, false, base, one for each 𝑥 , one for each 𝑥ഥ 𝑖𝑖
o Type 2: additional nodes for each clause 𝐶 𝑗
➢ 1-1 correspondence between valid 3-colorings of type 1 nodes and valid truth assignments:
o All literals with the same color as “true” node are set to true
o All literals with the same color as “false” node are set to false
➢ Claim: Fix any colors of type 1 nodes. There exists a valid 3-coloring of 𝐺 giving these colors to type 1 nodes if and only if the corresponding truth assignment is satisfying for 𝜑.
373F20 – Nisarg Shah 49
3-Coloring
➢ Create 3 new nodes T, F, and B, and connect them in a triangle
➢ Create a node for each literal, connect it to its negation and to B ➢ T-F-B must have different colors, and so must B-𝑥𝑖-𝑥ҧ𝑖
o Each literal has the color of T or F; its negation has the other color
o Valid 3-coloring ⇔ valid truth assignment (set all with color T to true)
…
373F20 – Nisarg Shah 50
3-Coloring
➢ We also need valid 3-coloring ⇔ satisfying truth assignment
o For each clause, add the following gadget with 6 nodes and 13 edges
o Claim: Clause gadget is 3-colorable ⇔ at least one of the nodes corresponding to the literals in the clause is assigned color of T
373F20 – Nisarg Shah 51
3-Coloring
➢ Claim: Valid 3-coloring ⇒ truth assignment satisfies 𝜑
o Suppose a clause 𝐶 is not satisfied, so all its three literals must be F 𝑖
o Then the 3 nodes in top layer must be B
o Then the first two nodes in bottom layer must be F and T o No color left for the remaining node ⇒ contradiction!
373F20 – Nisarg Shah 52
3-Coloring
➢ We just proved: valid 3-coloring ⇒ satisfying assignment ➢ Claim: satisfying assignment ⇒ valid 3-coloring
o Each clause has at least one literal with color T
o Exercise: Regardless of which literal has color T and which color (T/F) the other literals have, the clause widget can always be 3-colored
373F20 – Nisarg Shah 53
Review of Reductions
• If you want to show that problem B is NP-complete • Step 1: Show that B is in NP
➢ Some polynomial-size advice should be sufficient to verify a YES instance in polynomial time
➢ No advice should work for a NO instance
➢ Usually, the solution of the “search version” of the problem works
o But sometimes, the advice can be non-trivial
o For example, to check LP optimality, one possible advice is the values of both primal and dual variables, as we saw in the last lecture
373F20 – Nisarg Shah 54
Review of Reductions
• If you want to show that problem B is NP-complete
• Step 2: Find a known NP-complete problem A and reduce it
to B (i.e. show A ≤𝑝 B)
➢ This means taking an arbitrary instance of A, and solving it in
polynomial time using an oracle for B
o Caution 1: Remember the direction. You are “reducing known NP- complete problem to your current problem”.
o Caution 2: The size of the B-instances you construct should be polynomial in the size of the original A-instance
➢ This would show that if B can be solved in polynomial time, then A can be as well
➢ Some reductions are trivial, some are notoriously tricky…
373F20 – Nisarg Shah 55
Binary Integer Linear Programming (BILP)
• Problem
➢ Input: 𝑐 ∈ R𝑛, 𝑏 ∈ R𝑚, 𝐴 ∈ R𝑚×𝑛, 𝑘 ∈ R
➢ Question: Does there exist 𝑥 ∈ 0,1 𝑛 such that 𝑐𝑇𝑥 ≥ 𝑘 and 𝐴𝑥 ≤ 𝑏?
➢ Decision variant of “maximize 𝑐𝑇𝑥 subject to 𝐴𝑥 ≤ 𝑏” but instead of any 𝑥 ∈ R𝑛 with 𝑥 ≥ 0, we are restricting 𝑥 to binary.
➢ Does restricting search space make the problem easier or harder? o This is actually NP-complete!
373F20 – Nisarg Shah 56
BILP Feasibility
• An even simpler problem
➢ Special case where 𝑐 = 𝑘 = 0, so 𝑐𝑇𝑥 ≥ 𝑘 is always true
• Problem
➢ Input: 𝑏 ∈ R𝑚, 𝐴 ∈ R𝑚×𝑛
➢ Question: Does there exist 𝑥 ∈ 0,1 𝑛 such that 𝐴𝑥 ≤ 𝑏?
➢ Just need to find a feasible solution ➢ This is still NP-complete!
373F20 – Nisarg Shah 57
BILP Feasibility
• Claim: BILP Feasibility is in NP
➢ Recall: We need to show that there is a polynomial-time algorithm
which
o Can accept every YES instance with the right polynomial-size advice o Will not accept a NO instance with any advice
➢ Advice: simply a vector 𝑥 satisfying 𝐴𝑥 ≤ 𝑏 ➢ Algorithm: Check if 𝐴𝑥 ≤ 𝑏
➢ Simple!
373F20 – Nisarg Shah 58
BILP Feasibility
• Claim: 3SAT ≤𝑝 BILP Feasibility
➢ Take any formula 𝜑 of 3SAT
➢ Create a binary variable 𝑥𝑖 for each variable 𝑥𝑖 in 𝜑
o We’ll represent its negation 𝑥ҧ𝑖 with 1 − 𝑥𝑖
➢ For each clause 𝐶, we want at least one of its three literals to be TRUE
o Just make sure their sum is at least 1
oE.g.𝐶=𝑥1∨𝑥ҧ2∨𝑥ҧ3⇒𝑥1+ 1−𝑥2 + 1−𝑥3 ≥1 ➢ Easy to check that
o this is a polynomial reduction
o Resulting system has a feasible solution iff 𝜑 is satisfiable
373F20 – Nisarg Shah 59
So far…
• To establish NP-completeness of problem B, we always reduced 3SAT to B
➢ But we can reduce any other problem A that we have already established to be NP-complete
➢ Sometimes this might lead to a simpler reduction because A might already be “similar” to B
• Let’s see an example!
373F20 – Nisarg Shah 60
Vertex Cover
• Problem
➢ Input: Undirected graph 𝐺 = (𝑉, 𝐸), integer 𝑘
➢ Question: Does there exist a vertex cover of size 𝑘?
oThat is, does there exist 𝑆 ⊆ 𝑉 with 𝑆 = 𝑘 such that every edge is incident to at least one vertex in 𝑆?
Example:
• Does this graph have a vertex cover of size 4?
• Yes!
• Does this graph have a
vertex cover of size 3? • No!
= vertex cover
373F20 – Nisarg Shah 61
Vertex Cover
• Problem
➢ Input: Undirected graph 𝐺 = (𝑉, 𝐸), integer 𝑘
➢ Question: Does there exist a vertex cover of size 𝑘?
oThat is, does there exist 𝑆 ⊆ 𝑉 with 𝑆 = 𝑘 such that every edge is incident to at least one vertex in 𝑆?
Question:
• Did we see this graph in the last lecture?
• Yes!
• For independent set
of size 6
= vertex cover
= independent set
373F20 – Nisarg Shah 62
Vertex Cover
• Vertex cover and independent set are intimately connected! • Claim: 𝐺 has a vertex cover of size 𝑘 if and only if 𝐺 has an
independent set of size 𝑛 − 𝑘
• Stronger claim: 𝑆 is a vertex cover if and only if 𝑉\S is an independent set
373F20 – Nisarg Shah 63
Vertex Cover
• Claim: 𝑆 is a vertex cover if and only if 𝑉\S is an independent
set
• Proof:
➢ 𝑆 is a vertex cover
➢IFF:Forevery 𝑢,𝑣 ∈𝐸,atleastoneof{𝑢,𝑣}isin𝑆
➢ IFF: For every 𝑢, 𝑣 ∈ 𝐸, at most one of {𝑢, 𝑣} is in 𝑉\S ➢ IFF: No two vertices of 𝑉\S are connected by an edge
➢ IFF: 𝑉\S is an independent set ∎
373F20 – Nisarg Shah 64
Vertex Cover
• Claim: Independent Set ≤𝑝 Vertex Cover
➢ Take an arbitrary instance (𝐺, 𝑘) of Independent Set
➢ We want to check if there is an independent set of size 𝑘 ➢ Just convert it to the instance (𝐺, 𝑛 − 𝑘) of Vertex Cover ➢ Simple!
o A reduction from 3SAT would have basically repeated the reduction we already did for 3SAT ≤𝑝 Independent Set
➢ Note: I didn’t argue that Vertex Cover is in NP
o This is simple as usual. Just give the actual vertex cover as the advice.
373F20 – Nisarg Shah 65
Set Cover
• Problem
➢ Input: A universe of elements 𝑈, a family of subsets 𝑆, and an integer 𝑘 ➢ Question: Do there exist 𝑘 sets from 𝑆 whose union is 𝑈?
• Example
➢ 𝑈 = {1,2,3,4,5,6,7}
➢𝑆= 1,3,7, 2,4,6, 4,5, 1, 1,2,6 ➢ 𝑘 = 3? Yes! 1,3,7 , 4,5 ,{1,2,6}
➢ 𝑘 = 2? No!
373F20 – Nisarg Shah 66
Set Cover
• Claim: Set Cover is in NP
➢ Easy. Let the advice be the actual 𝑘 sets whose union is 𝑈.
• Claim: Vertex Cover ≤𝑝 Set Cover
➢ Given an instance of vertex cover with graph 𝐺 = (𝑉, 𝐸) and integer 𝑘,
create the following set cover instance
o Set 𝑈 = 𝐸
o For each 𝑣 ∈ 𝑉, 𝑆 contains a set 𝑆𝑣 of all edges incident on 𝑣
o Selecting 𝑘 set whose union is 𝑈 = selecting 𝑘 vertices such that union of their incident edges covers all edges
o Hence, the two problems obviously have the same answer
373F20 – Nisarg Shah 67
373F20 – Nisarg Shah 68
Cook-Levin Theorem
• We did not prove “the first NP-completeness” result • Theorem: 3SAT is NP-complete
➢ We need to prove this without using any other “known NP- complete” problem
➢ We want to directly show that every problem in NP can be reduced to 3SAT
• We will first reduce any NP problem to SAT, and then reduce SAT to 3SAT
373F20 – Nisarg Shah 69
Cook-Levin Theorem
• We’re not going to prove it in this class, but the key idea is as follows
➢ If a problem is in NP, then ∃ Turing machine 𝑇(𝑥, 𝑦) which
o takes as input a problem instance 𝑥 and an advice 𝑦 of size 𝑝(|𝑥|) o verifies in 𝑞(|𝑥|) time whether 𝑥 is a YES instance
o both 𝑝 and 𝑞 are polynomials
➢ 𝑥 is a YES instance iff ∃𝑦 𝑇 𝑥, 𝑦 = 𝐴𝐶𝐶𝐸𝑃𝑇
373F20 – Nisarg Shah 70
Cook-Levin Theorem
• 𝑥 is a YES instance iff ∃𝑦 𝑇 𝑥, 𝑦 = 𝐴𝐶𝐶𝐸𝑃𝑇
NOT IN SYLLABUS
➢ We need to convert ∃𝑦 𝑇 𝑥, 𝑦 = 𝐴𝐶𝐶𝐸𝑃𝑇 into whether a SAT formula 𝜑 is satisfiable
• Recall that a Turing machine 𝑇 consists of a memory tape, a head pointer, a state, and a transition function
• What describes 𝑇 at any given step of its computation?
➢ What is written in each cell of its memory tape?
➢ Which cell of the tape is the read/write head currently pointing to? ➢ What state is the Turing machine in?
373F20 – Nisarg Shah 71
Cook-Levin Theorem
• 𝑥 is a YES instance iff ∃𝑦 𝑇 𝑥, 𝑦 = 𝐴𝐶𝐶𝐸𝑃𝑇
NOT IN SYLLABUS
➢ We need to convert ∃𝑦 𝑇 𝑥, 𝑦 = 𝐴𝐶𝐶𝐸𝑃𝑇 into ∃𝑧 𝜑 𝑧 = 𝑇𝑅𝑈𝐸, where 𝑧 consists of Boolean variables and 𝜑 is a SAT formula
• Variables:
➢ 𝑇 = True if machine’s tape cell 𝑖 contains symbol 𝑗 at step 𝑘 of the
computation
➢ 𝐻 = True if the machine’s read/write head is at tape cell 𝑖 at step 𝑘
of the computation
➢ 𝑄𝑞,𝑘 = True if machine is in state 𝑞 at step 𝑘 of the computation
➢ Cell index 𝑖 and computation step 𝑘 only need to be polynomially large as 𝑇 works in polynomial time
𝑖,𝑗,𝑘
𝑖,𝑘
373F20 – Nisarg Shah 72
Cook-Levin Theorem
• 𝑥 is a YES instance iff ∃𝑦 𝑇 𝑥, 𝑦 = 𝐴𝐶𝐶𝐸𝑃𝑇
NOT IN SYLLABUS
➢ We need to convert ∃𝑦 𝑇 𝑥, 𝑦 = 𝐴𝐶𝐶𝐸𝑃𝑇 into ∃𝑧 𝜑 𝑧 = 𝑇𝑅𝑈𝐸, where 𝑧 consists of Boolean variables and 𝜑 is a SAT formula
• Clauses:
➢ Express how the variables must be related using the transition
function
➢ Express that the Turing machine must reach the state 𝐴𝐶𝐶𝐸𝑃𝑇 at some step of the computation
• This establishes that SAT is NP-complete. • Next: SAT ≤𝑝 3SAT.
373F20 – Nisarg Shah 73
Cook-Levin Theorem
• Claim: SAT ≤𝑝 3SAT
➢ Take an instance 𝜑 = 𝐶 ∧ 𝐶 ∧ ⋯ of SAT
12
➢ Replace each clause with multiple clauses with exactly 3 literals each ➢ For a clause with one literal, 𝐶 = l1:
o Add two variables 𝑧1, 𝑧2, and replace 𝐶 with four clauses l∨𝑧∨𝑧 ∧l∨𝑧ҧ∨𝑧 ∧l∨𝑧∨𝑧ҧ ∧l∨𝑧ҧ∨𝑧ҧ
112112112112 o Verify that this is logically equivalent to l1
➢ For a clause with two literals, 𝐶 = (l1 ∨ l2):
o Add variable 𝑧1 and replace it with the following:
l∨l∨𝑧 ∧l∨l∨𝑧ҧ 121121
o Verify that this is logically equal to l1 ∨ l2
373F20 – Nisarg Shah 74
Cook-Levin Theorem
• Claim: SAT ≤𝑝 3SAT
➢ For a clause with three literals, 𝐶 = l1 ∨ l2 ∨ l3:
o Perfect. No need to do anything!
➢ For a clause with 4 or more literals, 𝐶 = (l1 ∨ l2 ∨ ⋯ ∨ l𝑘 ):
o Add variables 𝑧1, 𝑧2, … , 𝑧𝑘−3 and replace it with: l∨l∨𝑧 ∧l∨𝑧ҧ∨𝑧 ∧l∨𝑧ҧ∨𝑧 ∧⋯
121312423
∧ l ∨𝑧ҧ ∨𝑧 ∧ l ∨l ∨𝑧ҧ 𝑘−2 𝑘−4 𝑘−3 𝑘−1 𝑘 𝑘−3
o Check:
• If any l𝑖 is TRUE, then there exists an assignment of 𝑧 variables
to make this TRUE
• If all l𝑖 are FALSE, then no assignment of 𝑧 variables will make this TRUE
373F20 – Nisarg Shah 75
NP vs co-NP
• Complements of each other
➢ NP = short proof for YES, co-NP = short proof for NO
➢ If a problem “Does there exist…” is in NP, then its complement “Does there not exist…” is in co-NP, and vice-versa
➢ The same goes for NP-complete and co-NP-complete
• Example
➢ SAT is NP-complete (“Does there exist 𝑥 satisfying 𝜑?”)
o So “Does there exist no 𝑥 satisfying 𝜑?”, i.e., “Is 𝜑 always FALSE?” is coNP-complete
➢ Then, Tautology (“Is 𝜑 always TRUE?”) is also coNP-complete
373F20 – Nisarg Shah 76
NP ∩ co-NP
• Clearly, P ⊆ NP ∩ co-NP
➢ No advice needed; can just solve the problem in polytime ➢ Major open question: Is P = NP ∩ co-NP?
• NP ∩ co-NP: Short proof of both YES and NO
➢ Hunt for problems not known in P but still in NP ∩ co-NP
373F20 – Nisarg Shah 77
NP ∩ co-NP
• Linear programming
➢ [Gale–Kuhn–Tucker 1948]: LP is in NP ∩ co-NP
➢ Question: max objective value ≥ threshold?
➢ Proof of YES: Provide a feasible solution with objective ≥ threshold ➢ Proof of NO: Provide optimal primal and dual solutions
373F20 – Nisarg Shah 78
NP ∩ co-NP
• Linear programming
➢ But later, Khachiyan [1979] proved that LP is in P
373F20 – Nisarg Shah 79
NP ∩ co-NP
• Primality testing (“Is 𝑛 a prime?”)
➢ [Pratt 1975]: PRIMES is in NP ∩ co-NP
➢ Proof of NO: Easy, provide a non-trivial factor ➢ Proof of YES: relies on interesting math
373F20 – Nisarg Shah 80
NP ∩ co-NP
• Primality testing (“Is 𝑛 a prime?”)
➢ Later, Agrawal, Kayal, and Saxena [2004] proved that PRIMES is in P
o Milestone result!
373F20 – Nisarg Shah 81
NP ∩ co-NP
• Factoring (“Does 𝑛 have a factor ≤ 𝑘?”) ➢ FACTOR is in NP ∩ co-NP
o Proof of YES: Just present such a factor o Proof of NO:
• Present the entire prime factorization of 𝑛 along with a short proof that each presented factor is a prime
• Verifier TM can check that each factor is indeed a prime, their product is indeed 𝑛, and none of the factors is ≤ 𝑘
• Actually, proofs of primality are not required anymore since we know the TM can just run the AKS algorithm to check if the factors are prime
373F20 – Nisarg Shah 82
NP ∩ co-NP
• Factoring (“Does 𝑛 have a factor ≤ 𝑘?”) ➢ Major open question: Is FACTOR in P?
o Basis of several cryptographic procedures ➢ Challenge: Factor the following number.
74037563479561712828046796097429573142593188889231289 08493623263897276503402826627689199641962511784399589 43305021275853701189680982867331732731089309005525051 16877063299072396380786710086096962537934650563796359
RSA-704
($30,000 prize if you can factor it)
373F20 – Nisarg Shah 83
NP ∩ co-NP
• Factoring (“Does 𝑛 have a factor ≤ 𝑘?”)
➢ [Shor 1994]: We can factor an 𝑛-bit integer in 𝑂(𝑛3) steps on a
quantum computer.
➢ *Scalable* quantum computers can help o 2001: Factored 15 = 3 x 5
o 2012: Factored 21 = 3 x 7
373F20 – Nisarg Shah 84
Other Complexity Classes
• Based on the exact time complexity ➢ DTIME(𝑛), NTIME(𝑛2), …
o Deterministic / nondeterministic time complexity • Based on space complexity
➢ DSPACE(𝑛), NSPACE(log 𝑛)
• Using randomization
➢ ZPP (expected polynomial time, no errors)
o Is P = ZPP?
• Allowing probabilistic errors
➢ RP (polynomial time, one-sided error) ➢ BPP (polynomial time, two-sided erros)
373F20 – Nisarg Shah 85