Assignment No.
-6
Branch: CSE/CYS/BC Subject: FLAT Subject Code: BTCS-502-18
Date of Giving: Date of Submission: 27/08/24 Max. Marks: 10
Q. Statement Bloom’s taxonomy CO/CO’s Marks
No. Level (PAQIC) Mapped
1 Prove that the language Level I CO6 3
L={⟨M⟩∣M is a TM and L(M) is
infinite}L = \{\langle M\rangle \mid M
\text{ is a TM and } L(M) \text{ is
infinite}\}L={⟨M⟩∣M is a TM and L(M)
is infinite}
is undecidable by applying Rice’s
Theorem, explaining why the property is
non-trivial.
2 Define the universal language Level III CO6 2
Lu={⟨M,w⟩∣M accepts w}L_u =
\{\langle M,w\rangle \mid M \text{
accepts } w\}Lu ={⟨M,w⟩∣M accepts
w}
3 Define the classes NP and co-NP, and Level II CO6 2
explain why problems in NP have
efficiently verifiable certificates.
b) Define polynomial-time many-one
reduction (≤pm\leq_p^m≤pm ).
c) Provide an example showing how
Clique ≤_p^m Vertex Cover,
indicating the polynomial
transformation.
4 Demonstrate that the Hamiltonian Cycle Level II CO6 3
problem is NP-complete.
b) Define the Partition problem and
outline a polynomial-time reduction from
Subset Sum to Partition, explaining why
Partition is NP-complete.
PAQIC ( Program Assessment & Quality Improvement Cell) REMARKS
HoD’s Signature PAQIC Member’s signature Subject Teacher’s Signature
Solution
Rice’s Theorem & Undecidability
Claim:
L={⟨M⟩∣M is a TM and L(M) is infinite}L = \{\langle M\rangle \mid M\text{ is a TM and
}L(M)\text{ is infinite}\}L={⟨M⟩∣M is a TM and L(M) is infinite}
is undecidable.
Solution:
• The property “L(M)L(M)L(M) is infinite” is non-trivial (some TMs recognize infinite
languages; some do not). It depends solely on the language recognized—a semantic
property.
• Rice's Theorem states that any non‑trivial semantic property of r.e. languages is
undecidable youtube.com+15courses.grainger.illinois.edu+15people.seas.harvard.edu+15.
Therefore, LLL is undecidable.
2. Universal Language & Diagonalization
Definitions:
Lu={⟨M,w⟩∣M accepts w},Lu‾={⟨M,w⟩∣M does not accept w}L_u = \{\langle M,w\rangle \mid M
\text{ accepts } w\},\quad \overline{L_u} = \{\langle M,w\rangle \mid M \text{ does not
accept } w\}Lu ={⟨M,w⟩∣M accepts w},Lu ={⟨M,w⟩∣M does not accept w}
Solution:
• Recursively enumerable: LuL_uLu is recognized by a universal TM that simulates MMM on
www and accepts if it halts and accepts; it may run forever otherwise → r.e. but not
necessarily decider.
• Non-recursive: Assume a decider exists → leads to contradiction via diagonalization:
construct a TM DDD that, on input ⟨M⟩\langle M\rangle⟨M⟩, simulates MMM on
⟨M⟩\langle M\rangle⟨M⟩ and loops vs rejects oppositely → contradiction like the standard
halting proof.
Thus, LuL_uLu is r.e. but not recursive.
3. Cook–Levin: SAT is NP-Complete
Outline:
1. SAT ∈ NP:
Given a Boolean formula, a guess (assignment) can be verified in polynomial time — clearly
in NP
courses.grainger.illinois.edunumberanalytics.com+2pages.cs.wisc.edu+2baeldung.com+2.
2. SAT is NP‑hard:
For any language L∈NPL\in \text{NP}L∈NP, let MMM be an NTM that decides LLL in
polynomial time. We build a polynomial-time reduction fff that maps an input xxx to a
Boolean formula φ\varphiφ encoding the accepting computation tableau of MMM on xxx.
a. φ\varphiφ asserts correct start, transitions, and existence of accept state.
b. x∈L ⟺ φx \in L \iff \varphix∈L⟺φ is satisfiable.
Thus SAT is NP-hard
faculty.cc.gatech.edupeople.seas.harvard.edunumberanalytics.com.
Hence, by Cook‑Levin theorem, SAT is NP‑complete.
4. P vs NP, co‑NP, & Polynomial-Time Reduction
a) Definitions:
• NP: Languages decidable by an NTM in polynomial time (i.e., certificate verifiable in
poly‑time).
• co‑NP: Complements of NP languages.
b) Many-one (Karp) reduction:
A function fff computable in polynomial time such that
x∈A ⟺ f(x)∈Bx \in A \iff f(x) \in Bx∈A⟺f(x)∈B
This ensures solving B efficiently implies solving A efficiently.
c) Example:
Clique ≤ₚ Vertex Cover:
Transform graph GGG, kkk for Clique into (G‾,∣V∣−k)(\overline{G}, |V|-k)(G,∣V∣−k) for Vertex
Cover.
• A clique of size kkk in GGG corresponds to covering all edges in the complement by choosing
the other ∣V∣−k|V|-k∣V∣−k vertices — this is a valid p-time reduction.
5. NP-Complete Problems in Graphs and Numbers
a) Hamiltonian Cycle:
• H-CYCLE ∈ NP: nondeterministically guess a cycle and verify each edge in polynomial time.
• NP-hardness: Usually reduce from e.g. 3-SAT or CLIQUE, constructing gadget-based
transformations.
b) Partition:
• Partition: Given integers, can they be split into two subsets with equal sum?
• NP-Completeness: Known NP-hard via reduction from Subset Sum.
Each instance {ai}\{a_i\}{ai }, total sum SSS, decide if subset sums to S/2S/2S/2.
The reduction constructs the Partition instance directly from Subset Sum, ensuring
equivalence.
