Automata Theory Non Deterministic Polynomial Time Online Exam Quiz
Automata Theory Non Deterministic Polynomial Time GK Quiz. Question and Answers related to Automata Theory Non Deterministic Polynomial Time. MCQ (Multiple Choice Questions with answers about Automata Theory Non Deterministic Polynomial Time
Which of the following are not in NP?
Options
A : All problems in P
B : Boolean Satisfiability problems
C : Integer factorization problem
D : None of the mentioned
What does NP stands for in complexity classes theory?
Options
A : Non polynomial
B : Non-deterministic polynomial
C : Both (a) and (b)
D : None of the mentioned
A problem which is both _______ and _________ is said to be NP complete.
Options
A : NP, P
B : NP, NP hard
C : P, P complete
D : None of the mentioned
The hardest of NP problems can be:
Options
A : NP-complete
B : NP-hard
C : P
D : None of the mentioned
In terms of NTIME, NP problems are the set of decision problems which can be solved using a non deterministic machine in _______ time.
Options
A : O(n)
B : O(n1/2)
C : O(nk), k?N
D : None of the mentioned
Travelling sales man problem belongs to which of the class?
Options
A : P
B : NP
C : Linear
D : None of the mentioned
Which of the following contains NP?
Options
A : PSPACE
B : EXPSPACE
C : Both (a) and (b)
D : None of the mentioned
Which of the following does not belong to the closure properties of NP class?
Options
A : Union
B : Concatenation
C : Reversal
D : Complement
Which of the following can be used to define NP complexity class?
Options
A : Verifier
B : Polynomial time
C : Both (a) and (b)
D : None of the mentioned
Chemical Engineering Basics - Part 1 more Online Exam Quiz
Automata Theory Markup Languages
Automata Theory Multistack Machines Counter Machines
Automata Theory Multitape Turing Machine
Automata Theory Non Deterministic Finite Automata Introduction
Automata Theory Non Deterministic Turing Machines