Explore topic-wise MCQs in Automata Theory.

This section includes 5 Mcqs, each offering curated multiple-choice questions to sharpen your Automata Theory knowledge and support exam preparation. Choose a topic below to get started.

1.

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
Answer» E.
Discussion
2.

Which of the following can be used to define NP complexity class?

A. Verifier
B. Polynomial time
C. Both Verifier and Polynomial time
D. None of the mentioned
Answer» D. None of the mentioned
Discussion
3.

In terms of NTIME, NP problems are the set of decision problems which can be solved using a non deterministic machine in _______ time.

A. O(n)
B. O(n<sup>1/2</sup>)
C. O(n<sup>k</sup>), k N
D. None of the mentioned
Answer» D. None of the mentioned
Discussion
4.

Which of the following is incorrect for the given phrase
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
Answer» E.
Discussion
5.

State true or false?
Statement: If a problem X is in NP and a polynomial time algorithm for X could also be used to solve problem Y in polynomial time, then Y is also in NP.

A. true
B. false
Answer» B. false
Discussion