080230026 THEORY OF COMPUTATION QUESTION PAPERS

Course Code:  080230026
Course Name: THEORY OF COMPUTATION    Duration : 3.00 Hours
Max. Marks    : 100
 
PART - A (10 x 2 = 20 MARKS)
ANSWER ALL THE QUESTIONS

1.    What is Turing machine?
2.    Define Multitape Turing Machine.
3.    What is Mapping reducibility?
4.    Give the definition of linear bound automaton.
5.    What is Time complexity?
6.    Prove that CLIQUE is in NP.
7.    Define Probabilistic Turing machine.
8.    What is one - way permutation?
9.    What are the classes L and NL?
10.    Give the proof idea for FORMULA-GAME is PSPACE-complete.

PART - B (5 x 16 = 80MARKS)
ANSWER ALL THE QUESTIONS
11.    a)    i.    Give implementation-level description of Turing machines that decide the following language over the alphabet{0,1}
{w/w contains an equal number of 0s and 1s}.        
    (10)
        ii    Show that a language is Turing-recognizable if and only if some enumerators enumerates it.   
    (6)
.            (OR)   
    b)    i.    Show that Halting Problem in undecidable.    (10)
        ii.    Prove that ANFA is decidable.    (6)
               
12.    a)    i.     Prove that Recursive theorem.    (8)
        ii.    Show that MIN(TM) is not Turing-recognizable.    (8)
            (OR)   
    b)    i.    What is Post Correspondence Problem (PCP) and prove PCP is undecidable.    (16)
               
13.    a)    i.    Prove that HAMPATH is NP-complete.    (16)
            (OR)   
    b)    i.    Define and Explain Cook-Levin Theorem.    (16)
               
14.    a)    i.    Prove CIRCUIT-SAT is  NP Complete.    (8)
        ii.    Show that if P is an odd prime number Pr[PRIME accepts P]=1.    (8)
            (OR)   
    b)    i.    Prove NL= coNL    (10)
        ii.    Prove the theorem PATH is NL Complete.    (6)
               
15.    a)    i.    Prove that NL is a subset of NC^2.    (8)
        ii.    Prove that EQRPOB is in BPP.    (8)
            (OR)   
    b)    i.    Explain about Parallel Computation.    (16)
                                                        



Roll No:
Programme     : B.E.
Branch           : Computer Science and Engineering
Semester         : VI
Course Code:  080230026
Course Name: THEORY OF COMPUTATION    Duration : 3.00 Hours
Max. Marks    : 100
 
PART - A (10 x 2 = 20 MARKS)
ANSWER ALL THE QUESTIONS

1.    Give the difference between FA and TM.
2.    What is meant by halting problem?
3.    Define Turing reducible
4.    Find a match in the following instance of PCP.
{[ab/abab],[b/a],[aba/b],[aa/a]}
5.    Define class P and NP completeness.
6.    State the True or False for the following statement
(i) n^2=o(log^2 n)
(ii) nlogn=o(n^2)
7.    Define trapdoor function.
8.    Prove that CIRCUIT-VALUE is p-complete?
9.    Define EXSPACE-complete.
10.    Define PSPACE and PSPACE-complete?

PART - B (5 x 16 = 80 MARKS)
ANSWER ALL THE QUESTIONS

11.    a)    i.    Prove that every CFL is decidable.    (8)
        ii    Show that EQ(DFA) is a decidable language.    (8)
.            (OR)   
    b)    i.    Prove that a language is decidable if and only if it is Turing-recognizable and co-Turing recognizable.    (10)
        ii.    Prove that ADFA is decidable.    (6)
               
12.    a)    i.    Prove that HALT(TM) is decidable.    (8)
        ii.    Prove that EQ(TM) is neither Turing-recognizable nor Co-Turing-recognizable.    (8)
            (OR)   
    b)    i.    Prove the theorem using reducibility concept: ETM is undecidable.    (10)
        ii.    Prove REGULARTM is undecidable.     (6)
               
13.    a)    i.     Prove that every CFL is a member of P.    (10)
        ii.    Show that SUBSET-SUM is in NP.    (6)
            (OR)   
    b)    i.    State and Prove 3SAT is polynomial time reducible to CLIQUE.    (10)
        ii.    Prove VERTEX CONVER is NP Complete.    (6)
               
14.    a)    i.    State and Prove that Savitch's theorem.                        (16)
            (OR)   
    b)    i.    Prove  an Oracle A exists whereby PA=NPA,
           an Oracle B exists whereby PB=NPB.    (10)
        ii.    Prove EQREX↑ is EXPSPACE complete.    (8)
               
15.    a)    i.    Prove IP = PSPACE.    (10)
        ii.    Prove the Theorem. A is a polynomial time algorithm that produces a vertex cover of G that is no max than twice as large as a smallest vertex cover.    (6)
            (OR)   
    b)    i.    Explain about cryptography concept.    (16)