+1-315-636-4485
+91 98151-74050 
This quiz contains MCQs on non-deterministic polynomial time, problem-solving in polynomials, node covers and Hamilton circuit problems.
If the number of steps required to solve a problem is O(nk), then the problem is said to be solved in
Non-polynomial time
Polynomial time
Infinite time
None of the above
The value of constants like p and e can be calculated in
Polynomial time
Non-polynomial time
Cannot be calculated
None of the above
Which of the following cannot be solved using polynomial time?
Linear programming
Greatest common divisor
Maximum matching
None of the above
The complexity class P consists of all the decision problems that can be solved by __ using a polynomial amount of computation time.
Pushdown automata
DFA
NDFA
Deterministic Turing machine
A generalization of the P class can be
PTIME
DTIME
NP
None of the above
Which of the following options are correct with reference to P-complete problems?
Used for the problems which are difficult to solve in limited space
Every problem in P can be reduced to it using proper reductions
Complete problem for complexity class P
All of the above
A problem X belongs to the P complexity class if there exists __ algorithm to solve that problem, such that a polynomial binds the number of steps of the algorithms in n, where n is the length of the input.
1
2
3
All of the above
Given a Turing machine, an input for the machine, and a number T(unary), the problem to the machine halting on that input within the first T-steps is P-complete. True or false?
True
False
Which of the following is a P-complete type of problem?
Circuit value problem
Linear programming
Context-free grammar membership
All of the above
If the input is binary in the above problem, to which class does the problem belong?
EXPSPACE
DLOGTIME
EXPTIME-complete
All of the above
__ represent(s) an exact cover problem.
Incidence matrix
Bipartite graph
Both incidence matrix and bipartite graph
None of the above
Which of the following problems were reduced to Knapsack?
Exact cover
Max cut
0-1 integer programming
None of the above
For which of the following does the greedy algorithm find a minimal vertex cover in polynomial time?
Tree graphs
Bipartite graphs
All of the above
None of the above
Hamilton’s circuit problem can have the following version(s) as per the input graph
Directed
Undirected
Both directed and undirected
None of the above
Hamilton’s circuit problem is a particular case of
The travelling salesman problem
The halting problem
The hitting set
None of the above
