NP
No Problem!
Definition 1
• 𝑁𝑃 = {𝐿: 𝐿 decidable by a polynomial time nondeterministic TM}
)𝑘𝑛(𝐸𝑀𝐼𝑇𝑁N∈𝑘ڂ =𝑃𝑁•
= 𝑛𝑓𝐸𝑀𝐼𝑇𝑁•
{𝐿: 𝐿 is a language decidable by an 𝑂 𝑓 𝑛 nondeterministic TM}
𝑃𝑁 ⊆ 𝑃 •

Running Time for nondeterministic TMs
• is the maximum number of steps the TM uses on any branch of its computation
NP Definition 2
• Note that the definition is based on nondeterministic TMs • 𝑁𝑃 = {𝐿: 𝐿 has a polynomial time verifier}
• What is a verifier?
Verifiers
• Given a language L, a TM V is called a verifier for L if 𝐿={𝑠:forsomestring𝑐,𝑉accepts 𝑠,𝑐 }
• When we say polynomial time verifier, we mean in the length of s alone (this implicitly requires that the size of 𝑐 is poly in s)
• c is called a certificate or witness (extra information)
• Suppose a language L is verifiable by the machine V, then
•If𝑥∈𝐿,then∃𝑦𝑉 𝑥,𝑦 accepts(thereisaproof𝑦that𝑥isin𝐿) •If𝑥∉𝐿,then∀𝑦𝑉 𝑥,𝑦 doesnotaccept
Intuition (Subset Sum problem)
•𝐿 = {𝑆⊆Z∶
𝑆 has a nonempty subset whose 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑠 𝑎𝑑𝑑 𝑢𝑝 𝑡𝑜 0}
• Input: A finite set of integers • Output: Yes/No
• Yes, if A has a nonempty subset of numbers that add up to 0 • No, otherwise
Deciding 𝐿
• Given a finite set of integers 𝑇 = {−7, −3, −2, 5, 8} , say.
• A computer goes through all nonempty subsets of 𝑇, and adds up their elements
• Going through the subsets takes exponential time in the size of the set
• Adding the elements in one of them takes polynomial time
Relation to nondeterministic TM
• Finding a subset could happen in polynomial time by luck (nondeteministic choice)
• On the previous page we described a deterministic way
Verifying for L
• Membership in 𝐿 can be verified within polynomial time (a number of
steps that follows a polynomial function in the size of the input set) • For 𝑇 = {−7, −3, −2, 5, 8} given before, there is 𝑐 = {−3, −2,5}
𝑐 is a subset of 𝑇, and the elements of 𝑐 add up to 0
• 𝑐 witnesses/proves/verifies that 𝑇 is in 𝐿
What is the verifier V in the previous example?
• 𝑉 takes as input two finite sets of integers (or two inputs, each is a finite set of integers)
1. 𝑉 checks if the second input set is a subset of the first
2. 𝑉 adds the elements in the second input and checks if the sum is 0
• 1 happens in polytime in the size of the first input • 2 happens in polytime in the size of the first input?
A Famous Problem (factorization)
• Find the prime factors of a natural number (large one)
• This requires trying many pairs of numbers
• However, given a factorization, it can be verified just by multiplication
• Note that this is different problem from deciding if a number is prime or not
More intuition
• Givenanequation
• Find a solution (NP)
• Or given a solution and check it works (P)
More and more
• Given a theorem
• Prove it (NP)
• OR given a proof and check it works (P)
P ≠ NP
P = NP.
P=NP?
• If the solution to a problem can be verified in polynomial time, can it be found in polynomial time?
• At least it gives hope, the hope that there is an efficient solution
NP-completeness
• A language L is NP-complete if (two things):
1. L is in the class NP
2. Every language L’ in NP is p-reducible to L
• NP-complete sets are the hardest
If to prove P=NP
• This requires a proof that some NP-complete language is in P
• In other words, take a problem which is known to be NP-complete,
then show that there is a polynomial time solution for it
• The majority of NP problems which seem to require exponential time are NP-complete
Wisdom from Sipser
• Sipser points out that some algorithms for NP-complete problems exhibit exponential complexity only in the worst-case scenario and that, in the average case, they can be more efficient than polynomial-time algorithms (even more than polytime)
• Instead of spending all of your time looking for a fast algorithm, you can spend half your time looking for a fast algorithm and the other half of your time looking for a proof of NP-completeness.
• On the practical side, the phenomenon of NP-completeness may prevent wasting time searching for a nonexistent polynomial time algorithm
SAT (The Booelan satisfiability problem)
• Given a Boolean formula, find an assignment that satisfies it
• Example of a Boolean formula: ¬𝑃&𝑄 OR (𝑃&¬𝑍)
• Example of a satisfying assignment (solution):
𝑃 = 𝐹𝐴𝐿𝑆𝐸,𝑄 = 𝑇𝑅𝑈𝐸,𝑍 = 𝐹𝐴𝐿𝑆𝐸
• Sipser uses small letter for the variables, and 1,0 for True, False
SAT
• 𝑆𝐴𝑇 = {𝜑: 𝜑 is a satisfiable Boolean formula}
• This is the first known NP-complete problem (language) • Proved by Stephen Cook here at U of T in 1971
• Independently proved by Leonid Levin
• Cook-Levin theorem: SAT is NP-complete
Algorithms for SAT
• Only algorithms with exponential worst-case scenario
Remarks
• We use only the connectives ¬, &, OR, they are more than enough to express all logical formulas without quantifiers
• In fact, ¬, & (or ¬, OR ) are enough, but having &, OR together makes life easier and easily mimicked by electrical circuits
• Boolean formulas can take many shapes, but any Boolean formula is equivalent to a CNF (conjunctive normal form)
CNF
•𝑥∨¬𝑥∨¬𝑥∨𝑥 ∧𝑥∨¬𝑥∨𝑥 ∧¬𝑥 12343566
3CNF
• Every clause has three literals
• Example: 𝑥1 ∨¬𝑥2 ∨¬𝑥3 ∧ 𝑥3 ∨¬𝑥5 ∨𝑥6
• Every Boolean formulas is equisatisfiable to a 3CNF one
i.e., given a CNF formula, we can transform it to a 3CNF formulas such that the first formula is satisfiable iff the second is satisfiable.
3SAT
•3𝑆𝐴𝑇 ={𝜑:𝜑isasatisfiable3CNFformula} • 3SAT is also NP-complete
• The proof is a modification of the proof for SAT
Subset Sum (general)
• Inputs: an integer value (target) t, and a set of integers 𝑎1, … , 𝑎𝑛 • Output: YES if there is a subset that adds up to t, NO otherwise
𝑥,…,𝑥,σ𝑙 𝑦=𝑡} 1 𝑛 𝑖=1𝑖
• SUBSET-SUM is NP-complete
•SUBSET-SUM={𝑆,𝑡:𝑆= 𝑥,…,𝑥 ,andforsome 𝑦,…,𝑦 ⊆
1𝑛 1𝑙
SUBSET-SUM is in NP • Proof: See Sipser (easy)
SUBSET-SUM is NP-complete
• We need to prove that all languages in NP are polynomial time
reducible to SUBSET-SUM
• How? We bring a language which we know is NP-complete, and show
that it is p-reducible to SUBSET-SUM
• Indeed, a possible proof shows that 3𝑆𝐴𝑇 ≤𝑝SUBSET-SUM