Formula Sheets: Undecidability | Theory of Computation - Computer Science Engineering (CSE) PDF Download

 Page 1


Undecidabilit y
Undecidabilit y Basics
T uring Recognizable and Decidable
• T uring Recognizable (RE): Language L if ? T uring Mac hine (TM) M suc h that L(M) = {w |
M halts and accepts w} .
• T uring Decidable (REC): Language L if ? TM M that halts on all inputs, accepts w ? L , rejects
w / ?L .
• Undecidable: Language neither in RE nor co-RE, or in RE but not REC.
Halting Problem
• Problem: H ={?M,w?|M halts on input w} .
• Unde cidable: No TM decides H for all ?M,w? .
Rice’s Theorem
• F or non-trivial prop ert y P of T uring-recognizable languages, {?M?| L(M) has prop ert y P} is unde-
cidable.
• Non- trivial: P holds for some L(M) but not all (e.g., L(M)?=Ø , L(M)?=S
*
).
Complexit y Classes
Class P
• Problems solv able b y deterministic TM in p olynomial time: O(n
k
) , wheren is input size,k is constan t.
Class NP
• Problems v erifiable b y deterministic TM in p olynomial time, or solv able b y nondeterministic TM in
p olynomial time.
NP-Completeness
• Problem is NP-complete if it is in NP and ev ery problem in NP reduces to it in p olynomial time.
• Reduction: ProblemA reduces toB if? p olynomial-time functionf suc h thatx?A ?? f(x)?B .
Key Problems
P ost Corresp ondence Problem (PCP)
• Input: Lists A ={a
1
,a
2
,...,a
n
} , B ={b
1
,b
2
,...,b
n
} of strings o v er S .
• Problem: Find sequence i
1
,i
2
,...,i
k
suc h that a
i1
a
i2
...a
i
k
=b
i1
b
i2
...b
i
k
.
• Undecidab le.
SA T (Bo ol ean Satisfiabilit y)
• Problem: G iv en Bo olean form ula in CNF, ? assignmen t making it true?
• NP-Com plete.
• Time Complexit y: O(2
n
) for brute force, where n is n um b er of v ariables.
V ertex Co v er
• Problem : Giv en graph G =(V,E) and k , ? v ertex set C ?V , |C|=k , co v ering all edges?
• NP-C omplete.
• Re duction: F rom SA T or Clique.
Clique
• Problem : Giv en graph G =(V,E) and k , ? complete subgraph with k v ertices?
1
Page 2


Undecidabilit y
Undecidabilit y Basics
T uring Recognizable and Decidable
• T uring Recognizable (RE): Language L if ? T uring Mac hine (TM) M suc h that L(M) = {w |
M halts and accepts w} .
• T uring Decidable (REC): Language L if ? TM M that halts on all inputs, accepts w ? L , rejects
w / ?L .
• Undecidable: Language neither in RE nor co-RE, or in RE but not REC.
Halting Problem
• Problem: H ={?M,w?|M halts on input w} .
• Unde cidable: No TM decides H for all ?M,w? .
Rice’s Theorem
• F or non-trivial prop ert y P of T uring-recognizable languages, {?M?| L(M) has prop ert y P} is unde-
cidable.
• Non- trivial: P holds for some L(M) but not all (e.g., L(M)?=Ø , L(M)?=S
*
).
Complexit y Classes
Class P
• Problems solv able b y deterministic TM in p olynomial time: O(n
k
) , wheren is input size,k is constan t.
Class NP
• Problems v erifiable b y deterministic TM in p olynomial time, or solv able b y nondeterministic TM in
p olynomial time.
NP-Completeness
• Problem is NP-complete if it is in NP and ev ery problem in NP reduces to it in p olynomial time.
• Reduction: ProblemA reduces toB if? p olynomial-time functionf suc h thatx?A ?? f(x)?B .
Key Problems
P ost Corresp ondence Problem (PCP)
• Input: Lists A ={a
1
,a
2
,...,a
n
} , B ={b
1
,b
2
,...,b
n
} of strings o v er S .
• Problem: Find sequence i
1
,i
2
,...,i
k
suc h that a
i1
a
i2
...a
i
k
=b
i1
b
i2
...b
i
k
.
• Undecidab le.
SA T (Bo ol ean Satisfiabilit y)
• Problem: G iv en Bo olean form ula in CNF, ? assignmen t making it true?
• NP-Com plete.
• Time Complexit y: O(2
n
) for brute force, where n is n um b er of v ariables.
V ertex Co v er
• Problem : Giv en graph G =(V,E) and k , ? v ertex set C ?V , |C|=k , co v ering all edges?
• NP-C omplete.
• Re duction: F rom SA T or Clique.
Clique
• Problem : Giv en graph G =(V,E) and k , ? complete subgraph with k v ertices?
1
• NP-Complete.
• Reduction: F rom SA T.
Hamiltonian Cycle
• Problem: Giv en graph G =(V,E) , ? cycle visiting eac h v ertex exactly once?
• NP- Complete.
• R eduction: F rom V ertex Co v er.
T ra v eling Salesman Problem (TSP)
• Prob lem: Giv en graph G with edge w eigh ts and k , ? cycle visiting all v ertices with total w eigh t =k ?
• NP- Complete.
• R eduction: F rom Hamiltonian Cycle.
2