gs gs101 Intractable Problems - Problem Solvable in Polynomial Time - Quiz No.1
gs gs101 Automata Theory Quiz
This quiz belongs to book/course code gs gs101 Automata Theory of gs organization. We have 92 quizzes available related to the book/course Automata Theory. This quiz has a total of 10 multiple choice questions (MCQs) to prepare and belongs to topic Intractable Problems. NVAEducation wants its users to help them learn in an easy way. For that purpose, you are free to prepare online MCQs and quizzes.
NVAEducation also facilitates users to contribute in online competitions with other students to make a challenging situation to learn in a creative way. You can create one to one, and group competition on an topic of a book/course code. Also on NVAEducation you can get certifications by passing the online quiz test.
Question 1: 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 mentioned
Question 2: The value of constants like p and e can be calculated in:
polynomial time
non-polynomial time
cannot be calculated
none of the mentioned
Question 3: Which of the following cannot be solved using polynomial time?
Linear Programming
Greatest common divisor
Maximum matching
None of the mentioned
Question 4: The complexity class P consist of all the decision problems that can be solved by ___________using polynomial amount of computation time.
Push Down automata
DFA
NDFA
Deterministic Turing machine
Question 5: A generalization of P class can be:
PTIME
DTIME
NP
None of the mentioned
Question 6: 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 mentioned
Question 8: Which of the following is a P-complete type of problem?
Circuit Value problem
Linear programming
Context free grammar membership
All of the mentioned
Question 10: In the above problem, if the input is binary, the class the problem belongs?
EXPSPACE
DLOGTIME
EXPTIME-complete
All of the mentioned
Online Quizzes of gs101 Automata Theory
Other Classes Of Problems - Randomized Algorithm - Quiz No.1
gs gs101
Automata Theory Online Quizzes
Push Down Automata - DPDA and Ambiguous Grammars - Quiz No.1
gs gs101
Automata Theory Online Quizzes
