G1164

PART (^
Answer any two full questions, each carries 9 marks.

14(a) State the 3-colourability problem.

15

16

17

18

19

(b) Prove that 3-colourability is an element of class NP

© Prove that 3-colourability problem is NP-Complete

(a)
(b)
(a)
(b)

(a)
(b)

(a)
(b)
(a)
(b)

What is Totally Quantified Boolean Formula (TBQF).Write an Example?
Prove that TBQF is PSPACE-Complete.
Define the PATH Problem in Graph theory.
Prove that NL=CO-NL using PATH problem
PART D
Answer any two full questions, each carries 12 marks.
Define the complexity classes BPP.
Prove that the problem PRIME={nJn is a prime number in binary} is in the
complexity class BPP.
Write short note on Interactive proof system.
Design a randomized algorithm to solve K-SAT problem.
Define the VERTEX COVER Problem.
Design a polynomial time approximation algorithm for VERTEX COVER

EE

Pages: 2

(1)
(2)
(6)
(3)
(6)
(2)
(7)

(2)
(10)

(6)
(6)
(4)
(8)