T Naughton, CS NUIM, Back to CS403 home

Attempt all four questions from Section A and one question from Section B. Maximum marks 90.

Section A – Computational Complexity

Q1 What is computational complexity theory and why is it useful to computer scientists? [15 marks]

Q2 What do we mean when we say that computational complexity theory relies on the Invariance thesis? [15 marks]

Q3 What languages are in NP? Give an example of three NP languages with different complexities. [15 marks]

Q4 What does a polynomial reduction A<=B between two problems establish about their relative complexities? How could one use a reduction to prove non-membership of a class? [15 marks]

Section B – Turing machine programming

Q5 Write a Turing machine (TM) to find the modulus of two unary numbers. Initially, the tape head will be positioned at the beginning of the first number and the two numbers will be separated by a single blank. At halt, the TM head must be at the beginning of the output. For example, input "111  11" would be transformed into "1", and input "1111  11" would be transformed into "  ". [30 marks]

Q6 Write a TM to subtract two unary numbers. Initially, the tape head will be positioned at the beginning of the first number and the two numbers will be separated by a single blank. At halt, the TM head must be at the beginning of the output. For example, input "111  11" would be transformed into "1", and input "1111  11" would be transformed into "11". [15 marks]