Home / Engineering / Theory of Computation MCQs / Page 14

# Theory of Computation MCQs | Page - 14

Dear candidates you will find MCQ questions of Theory of Computation here. Learn these questions and prepare yourself for coming examinations and interviews. You can check the right answer of any question by clicking on any option or by clicking view answer button.

##
Q. 132) The set strings of 0's and 1's with atmost one pair consecutive one's-

##
Q. 133) The problem 3-SAT and 2-SAT are

##
Q. 134) Which of the following instances of the post correspondence problem has a viable sequence (a solution)?

##
Q. 135) Let FHAM be the problem of finding a Hamiltonian cycle in a graph G and DHAM be the problem of determining if a Hamiltonial cycle exists in a graph. Which one of the following is TRUE?

##
Q. 136) Consider three problems P1, P2 and P3. It is known that P1 has polynomial time solution and P2 is NP-complete and P3 is in NP. Which one of the following is true.

##
Q. 137) Which one of the following is the strongest correct statement about a finite language Lover a finite alphabet Σ?

##
Q. 138) Which one of the following is not decidable?

##
Q. 139) Which of the following statements are TRUE?
(1) The problem of determining whether there exists a cycle in an undirected graph is in P.
(2) The problem of determining whether there exists a cycle in an undirected graph is in NP.
(3) If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.

##
Q. 140) Consider a graph G = (V, E) where I V I is divisible by 3. The problem of finding a Hamiltonian cycle in a graph is denoted by SHAM3 and the problem of determining if a Hamiltonian cycle exits in such graph is denoted by DHAM3. The option, which holds true, is

### Explore Sets

Theory of Computation MCQs Set 1

Theory of Computation MCQs Set 2

Theory of Computation MCQs Set 3

Theory of Computation MCQs Set 4

Theory of Computation MCQs Set 5

Theory of Computation MCQs Set 6

Theory of Computation MCQs Set 7

Theory of Computation MCQs Set 8

Theory of Computation MCQs Set 9

Theory of Computation MCQs Set 10

Theory of Computation MCQs Set 11

Theory of Computation MCQs Set 12

Theory of Computation MCQs Set 13

### Explore More Categories

Click on category to learn MCQs of that category.Electronics and Communication Engineering