THEORY EXAMINATION (SEM–VI) 2016-17 COMPLEXITY THEORY

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.