Recall that
For the purpose of decision problems, the NTMs we will be working with are deciders:
1. they halt for any given input on all branches 2. they output accept/reject
A decider NTM accepts an input if at least one branch accepts
We say a decider NTM has time complexity (running time) 𝑓(𝑛) if 𝑓(𝑛) is the maximum number of steps to reach a halt over all branches over all inputs of size 𝑛
NP – Definition 1
𝑁𝑃 = {𝐿: 𝐿 decidable by a polynomial time NTM}
• 𝑁𝑇𝐼𝑀𝐸 𝑓 𝑛 ={𝐿:𝐿isalanguagedecidablebyan𝑂 𝑓 𝑛 NTM} )𝑘𝑛(𝐸𝑀𝐼𝑇𝑁 N∈𝑘ڂ = 𝑃𝑁 •
Remark: 𝑃 ⊆ 𝑁𝑃
NP – Definition 2
𝑁𝑃 = {𝐿: 𝐿 has a polynomial time verifier}
What is a verifier? It is a TM, nothing new. What is new is the relationship between such a TM and a language 𝐿
For a language 𝐿, a TM 𝑉 is called a verifier for 𝐿 if
𝐿 = {𝑠: for some string (certificate) 𝑐, 𝑉 accepts 𝑠, 𝑐 }
Consider the following language:
𝑆𝐴𝑇 = {𝜑 ∶ 𝜑 is a satisfiable Boolean formula} A verifier for 𝑆𝐴𝑇 would be a TM which takes as input
(Boolean formula, truth assignment) and decides whether the truth assignment satisfies the Boolean formula or not.
𝑆𝐴𝑇 is NP because we can build a polynomial time verifier for 𝑆𝐴𝑇
A polynomial time verifier for SAT
Def SAT_VERIFIER (boolean_formula , truth_assignment):
#a truth assignment is a list of TRUE and FALSE values
#a boolean_formula is a logical expression in some variables Compute the truth value of boolean_formula
if TRUE, return ACCEPT; else, REJECT
Def SAT_VERIFIER ((𝑥1˄¬𝑥3)˅𝑥2 , [ T , F , F ] ) = ACCEPT (which means verified) Def SAT_VERIFIER ((𝑥1˄¬𝑥3)˅𝑥2 , [ T , F , T ] ) = REJECT (which means not verified)
The string [ T , F , F ] is a certificate that (𝑥1˄¬𝑥3)˅𝑥2 is in 𝑆𝐴𝑇
The string [ T , F , T ] is not a certificate that (𝑥1˄¬𝑥3)˅𝑥2 is in 𝑆𝐴𝑇 (this certificate couldn’t verify that (𝑥1˄¬𝑥3)˅𝑥2 is in 𝑆𝐴𝑇)
SAT is in NP
Since there exists a polynomial time verifier for SAT, it is a language in NP, by the second definition of NP
We can prove that SAT is in NP using the first definition by showing that a polynomial time NTM decider exists
Here is a nondeterministic function that can decide Boolean satisfiability in polynomial time:
Def NDecider_SAT (boolean_formula):
Arbitrarily (nondeterministically) assign the variables of boolean_formula to
some truth values
If the result is True, Accept, else, Reject
NDecider_SAT((𝑥 ˄¬𝑥 )˅𝑥 ) 132
When NDecider_SAT takes, let’s say, (𝑥1˄¬𝑥3)˅𝑥2 as an input; one can imagine it arbitrarily choosing an assignment from
[T,T,T],[T,T,F],[T,F,T],[T,F,F],[F,T,T],[F,T,F],[F,F,T],[F,F,F] Then it runs Def SAT_VERIFIER ((𝑥1˄¬𝑥3)˅𝑥2 , chosen assignment)
Each possible choice corresponds to a possible branch of the NTM computation. Another way to imagine is:
arbitrarily choose a value for 𝑥1, then a value for 𝑥2, then a value for 𝑥3 , where now each choice corresponds to two ways of branching.
Verifier vs NTM
At this point, can you see from the example how each certificate corresponds to a branch of the NTM computation?
Also, can you see how running a verifier with a particular a certificate is the same as one branch of the NTM?
Exercise: Prove the equivalence of the two definitions of NP
NP-complete
NP-complete problems is a subclass NP
NP-complete={𝐿 ∶ 𝐿 ∈ 𝑁𝑃 ˄ ∀𝐿 ∈ 𝑁𝑃,𝐿′ ≤ 𝐿} 𝑝
Let 𝐿 be some language (decision problem). From this definition, it is easy to see that
if there exists some NP-complete language 𝐿 such that 𝐿 ≤𝑝 𝐿 , then 𝐿 has to be NP-
complete. This follows from the fact that the relation ≤𝑝 is transitive
The language 𝑆𝐴𝑇 is the first known NP-complete problem (Cook-Levin Theorem)
Remark: The class {𝐿 ∶ ∀𝐿 ∈ 𝑁𝑃, 𝐿′ ≤ 𝐿} is known as NP-hard 𝑝
3𝑆𝐴𝑇 = {𝜑 ∶ 𝜑 is a satisfiable 3CNF formula}
What is a 3CNF formula?
It is any Boolean formula on the shape:
𝑎∨𝑏∨𝑐 ∧⋯∧(𝑎∨𝑏∨𝑐) 111 𝑘𝑘𝑘
Where each 𝑎𝑖 , 𝑏𝑖 , 𝑐𝑖 is a literal, i.e. a variable or the negation of a variable. Here isanexample: 𝑥1 ∨¬𝑥2 ∨¬𝑥3 ∧ 𝑥3 ∨¬𝑥5 ∨𝑥6
Each bracket is known as a clause
CNF stands for Conjunctive Normal Form, and the number 3 stands for the fixed size of each clause
3SAT is NP-completen
Both 𝑆𝐴𝑇 and 3𝑆𝐴𝑇 are NP-complete
Clearly 3𝑆𝐴𝑇 is NP. In addition, one can show that 𝑆𝐴𝑇 ≤𝑝 3𝑆𝐴𝑇 by defining a polynomial time procedure (function) which can transform any Boolean formula into an equisatisfiable 3CNF formula.
Example:𝑥 ˅𝑥 transformsinto (𝑥 ˅𝑥 ˅𝑥 )˄(𝑥 ˅𝑥 ˅¬𝑥 ) 12 123123
Two Boolean formulas 𝜑, 𝜓 are equisatisfiable if they are both satisfiable or both not satisfiable. In other words,
𝜑 is satisfiable ⟺ 𝜓 is satisfiable
浙大学霸代写 加微信 cstutorcs
Prove that there is a computable procedure by which every Boolean formula can be converted to an equivalent CNF formula. The proof is here, so try to understand it and to write it yourself
Prove that there is a computable procedure by which every CNF formula can be transformed to an equisatisfiable 3CNF formula. A proof is here and here
Combine the two parts to show that 𝑆𝐴𝑇 ≤𝑝 3𝑆𝐴𝑇
Proving NP-hardness
In many situations, to prove that a given decision problem 𝐿 is NP- hard, we prove that 3𝑆𝐴𝑇 is polynomial time reducible to 𝐿
Prove that the following language is NP-hard:
𝐶𝐿𝐼𝑄𝑈𝐸 = { 𝐺, 𝑘 ∶ 𝐺 is an undirected graph with a 𝑘-clique }
A 𝑘-clique is a subgraph of size 𝑘 wherein every two vertices are connected by an edge
3𝑆𝐴𝑇 ≤𝑝 𝐶𝐿𝐼𝑄𝑈𝐸
The universe of 3𝑆𝐴𝑇 is the set of all 3CNF formulas
Theuniverseof𝐶𝐿𝐼𝑄𝑈𝐸isthesetofallpairsof 𝐺,𝑘 suchthat𝐺isanundirected graph and k is a natural number
To show that 3𝑆𝐴𝑇 ≤𝑝 𝐶𝐿𝐼𝑄𝑈𝐸, we need to: describe an effective (computable) procedurebywhichwecantransformany3CNFformula𝜑intoapair 𝐺,𝑘 (i.e., transform an instance of 3𝑆𝐴𝑇 to an instance of 𝐶𝐿𝐼𝑄𝑈𝐸). We want the procedure to have polynomial time complexity, and we want it to guarantee the following:
𝜑 is satisfiable ⟺ 𝐺 has a 𝑘 -clique 𝜑𝜑
𝜑 ∈3𝑆𝐴𝑇⟺(𝐺 ,𝑘 )∈𝐶𝐿𝐼𝑄𝑈𝐸 𝜑𝜑
Programming Help
We showed that 𝐶𝐿𝐼𝑄𝑈𝐸 is NP-hard Prove that 𝐶𝐿𝐼𝑄𝑈𝐸 is NP-complete
程序代写 CS代考 加QQ: 749389476
It is common to see the brackets around elements of a language. For example, you will find in Sipser’s book 𝐶𝐿𝐼𝑄𝑈𝐸 written as follows:
𝐶𝐿𝐼𝑄𝑈𝐸 = { 𝐺, 𝑘 : 𝐺 is an undirected graph with a 𝑘-clique } Or you will find
3𝑆𝐴𝑇 = { 𝜑 ∶ 𝜑 is a satisfiable 3CNF formula}
These brackets are used to remind the reader that we are looking at binary strings (or natural numbers) representing the entities between the brackets.
It is natural to feel that P ⊊ NP, but it is unknown There is no known proof (or disproof) that P ≠ NP
If P = NP , then every NP-complete problem will have a polynomial time solution
We have seen that given a Boolean formula 𝜑 , and an assignment (certificate) 𝑐 , we can verify in polynomial time if 𝑐 satisfies 𝜑
In that sense, we have the ability to easily verify if a given assignment satisfies a given formula
Does that somehow entail that there is an easy way (polynomial time) to decide if a given 𝜑 is satisfiable or not?
Does that somehow entail that there is an easy way (polynomial time) to produce a satisfying assignment (if it exists) if 𝜑 is satisfiable?
A philosophical question
Given a statement 𝑃, is the ability to (easily) verify a given proof for 𝑃 entail the ability to (easily) decide whether 𝑃 is provable or not?
Is the ability to (easily) verify a given proof for 𝑃 entail the ability to (easily) prove 𝑃?