COMPLEXITY THEORY – NCS062
B.Tech (SEM VI) | Section-wise Solved Answers
SECTION – A
(Explain the following – 2 marks each)
(a) Turing Machine
A Turing Machine is a mathematical model of computation that consists of an infinite tape, a read-write head, and a finite control unit. It is used to define what problems are computable.
(b) Parallel Computation
Parallel computation is a computing method where multiple processors execute different parts of a task simultaneously. It helps reduce execution time for large and complex problems.
(c) Diagonalisation
Diagonalisation is a proof technique used to show that certain problems or languages cannot be solved by any algorithm. It is commonly used to prove undecidability and hierarchy theorems.
(d) Uncomputable Function
An uncomputable function is a function for which no algorithm exists that can compute its output for every possible input. The Halting Problem is a classic example.
(e) NP-Complete Problem
An NP-Complete problem is a problem that is both in NP and as hard as any problem in NP. If any NP-Complete problem is solved in polynomial time, then all NP problems can be solved in polynomial time.
(f) Counting Problems
Counting problems focus on determining the number of solutions rather than deciding whether a solution exists. These problems often belong to the complexity class #P.
(g) Interactive Proof
An interactive proof system involves two parties: a prover and a verifier. The prover tries to convince the verifier that a statement is true through interaction, and the verifier uses randomness.
(h) Approximability and Inapproximability
Approximability refers to how closely an optimization problem can be solved near its optimal solution. Inapproximability means no efficient algorithm can approximate the solution within a certain bound.
(i) Adleman’s Theorem
Adleman’s theorem states that BPP (Bounded-error Probabilistic Polynomial time) is contained in P/poly, meaning randomized algorithms can be simulated using polynomial-size circuits.
(j) Fooling Set
A fooling set is a technique used to prove lower bounds in communication complexity by identifying inputs that confuse protocols into incorrect outputs.
SECTION – B
(Attempt any five – explained clearly)
(a) Complexity Classes and Their Relationship
Complexity classes group problems based on the resources required to solve them.
For example, P ⊆ NP ⊆ PSPACE ⊆ EXPTIME.
Problems in P are efficiently solvable, while NP problems are efficiently verifiable.
(b) Steps to Prove NP-Completeness
To prove a problem is NP-Complete, first show it belongs to NP. Then reduce a known NP-Complete problem to it using polynomial-time reduction.
(c) Randomized Quick Sort Algorithm
Randomized Quick Sort selects a pivot randomly instead of deterministically. This reduces the chance of worst-case performance and ensures expected time complexity of O(n log n).
(d) Circuit Satisfiability Problem
Circuit SAT asks whether there exists an input that makes a Boolean circuit output true. It belongs to NP because a satisfying input can be verified in polynomial time.
(e) Equivalence of Single and Multi-Tape Turing Machines
Multi-tape Turing Machines can be simulated by single-tape machines with only polynomial slowdown, proving both models are computationally equivalent.
(f) Gödel’s Incompleteness Theorem
Gödel’s theorem states that in any consistent formal system, there exist true statements that cannot be proven within the system. Example: statements about arithmetic truth.
(g) Rice’s Theorem
Rice’s theorem states that all non-trivial semantic properties of programs are undecidable. It is widely used to prove undecidability in complexity theory.
(h) Randomized Quick Sort Steps and Complexity
The algorithm randomly selects a pivot, partitions elements, and recursively sorts subarrays. Its expected time complexity is O(n log n).
SECTION – C
(Attempt any two – long answers)
(3) Complexity Classes: BPP, RP, coRP
BPP: Problems solvable with bounded error probability in polynomial time
RP: One-sided error randomized class
coRP: Complement of RP
These classes help understand the power of randomness in algorithms.
(4) Proof-Based Questions
(i) If a problem is in P, its complement is also in P because polynomial-time algorithms can be inverted easily.
(ii) If the complement of an NP-Complete problem is in NP, then NP = coNP, which would collapse major complexity class separations.
(5) Short Notes
Quantum Computation
Uses quantum bits and quantum mechanics to solve certain problems faster than classical computers.
Communication Complexity
Studies how much communication is needed between parties to compute a function.
Parallel Computation
Focuses on dividing tasks across multiple processors to achieve faster computation.
