1. Which of the given problems are NP-complete?
a) Node cover problems
b) Directed Hamilton Circuit Problem
c) Both (a) and (b)
d) None of the mentioned
View Answer
Explanation: Vertex cover or Node cover problem, and Hamilton Circuit problem, both are NP complete type of problems.
a) lambda calculus
b) C++
c) Lisp
d) All of the mentioned
View Answer
Explanation: Most of the programming languages, conventional or unconventional are turing complete. Functional languages like Lisp and Haskell are also turing complete.
3. Which aong the following are undecidable theories?
a) The first order theory of boolean algebra
b) The first order theory of Euclidean geomentry
c) The first order theory of hyperbolic geometry
d) The first order theory of the natural number with addition, multiplication, and equality
View Answer
Explanation: Tarski and Mostowski in 1949, established that the first order theory of natural numbers with addition, multiplication, and equality is an undecidable theory. Others mentioned are decidable theories.
4. Fill in the blank with reference to Rice’s theorem.
For any non-trivial property of __________ no general or effective method can decide whether an algorithm computes it with that property.
a) partial functions
b) piecewise functions
c) both (a) and (b)
d) none of the mentioned
View Answer
Explanation: A property of partial functions is called trivial if it holds for all partial computable functions or for none, and an effective decision method is called general if it decides correctly for every algorithm.
a) Step function
b) Step counting function
c) Inplace functions
d) None of the mentioned
View Answer
Explanation: If f is a step counting function, T is a TM halting in f(n) moves where n is the length of input string.
a) Communication Link
b) Adder
c) Stack
d) None of the mentioned
View Answer
Explanation: Idle is the state when data in form of packets is send and returns if NAK is received else waits for the NAK to be received.
Phrase :’solvable by non deterministic algorithms in polynomial time’
a) NP Problems
b) During control flow, non deterministic algorithm may have more than one choice
c) If the choices that non deterministic algorithm makes are correct, the amount of time it takes is bounded by polynomial time.
d) None of the mentioned
View Answer
Explanation: Primality testing is a simple example. To decide whether a number is prime or not, one simply selects non deterministically a number checks whether factors exist for the number or not.
a) O(n)
b) O(n1/2)
c) O(nk), k?N
d) None of the mentioned
View Answer
Explanation: The complexity class NP can be defined in terms of NTIME as:
NP=O(nk) for k ?N.
a) Verifier
b) Polynomial time
c) Both (a) and (b)
d) None of the mentioned
View Answer
Explanation: NP can be defined using deterministic turing machines as verifiers.
10. Which of the following are not in NP?
a) All problems in P
b) Boolean Satisfiability problems
c) Integer factorization problem
d) None of the mentioned
View Answer
Explanation: This is a list of some problems which are in NP:
a) All problems in P
b) Decision version of Integer factorization method
c) Graph Isomorphism Problem
d) All NP complete problems, etc.
a) Can simulate a two way tape
b) Upper track represents the head-right cells
c) Lower track represents the head-left cells
d) All of the mentioned
View Answer
Explanation: The upper track represents the cells of the original TM that are at the right of the initial head position. The lower track represents the cells to the left of the initial head position, but in reverse order.
a) Yes
b) No
c) Cannot be said
d) none of the mentioned
View Answer
Explanation: The symbols to left of the head of turing macine being simulated can be stored on the stack while the symbols on the right of the head can be placed on another stack. On each stack, symbols closer to the TM’s head are placed closer to the top of the stack than symbols farther from the TM’s head.
13. State true or false:
Statement: Turing Machine can change symbols on its tape, whereas the FA cannot change symbols on tape.
a) true
b) false
View Answer
Explanation: The following mentioned is the difference between 2-way FA and TM. Another instance is that TM has a read/write tape head while FA doesn’t.
14. A deterministic turing machine is:
a) ambiguous turing machine
b) unambiguous turing machine
c) non-deterministic
d) none of the mentioned
View Answer
Explanation: A deterministic turing machine is unambiguous and for every input, there is exactly one operation possible. It is a subset of non-deterministic Turing machines.
a) doubly
b) triple
c) quadratically
d) none of the mentioned
View Answer
Explanation: Thus, multitape turing machines cannot calculate any more functions than single tape machines.
