Automata Theory Questions and Answers – Problem Solvable in Polynomial Time

This set of Automata Theory Interview Questions and Answers for Experienced people focuses on “Problem Solvable in Polynomial Time”.

1. If the number of steps required to solve a problem is O(nk), then the problem is said to be solved in:
a) non-polynomial time
b) polynomial time
c) infinite time
d) none of the mentioned
View Answer

Answer: b
Explanation: Most of the operations like addition, subtraction, etc as well as computing functions including powers, square roots and logarithms can be performed in polynomial time. In the given question, n is the complexity of the input and k is some non negative integer.

2. The value of constants like p and e can be calculated in:
a) polynomial time
b) non-polynomial time
c) cannot be calculated
d) none of the mentioned
View Answer

Answer: a
Explanation: The value of such constants can be calculated using algorithms which have time complexity in terms if O(nk) i.e polynomial time.

3. Which of the following cannot be solved using polynomial time?
a) Linear Programming
b) Greatest common divisor
c) Maximum matching
d) None of the mentioned
View Answer

Answer: d
Explanation: In graph theory, a matching or independent edge set in a graph G is a set of edges without common vertices. Given a graph (V, E), a matching M in G is a set of pairwise non adjacent edges i.e. no two edges share a common vertex.
advertisement
advertisement

4. The complexity class P consist of all the decision problems that can be solved by ___________using polynomial amount of computation time.
a) Push Down automata
b) DFA
c) NDFA
d) Deterministic Turing machine
View Answer

Answer: d
Explanation: All the decision problems that can be solved using a Deterministic turing machine using polynomial time to compute, all belong to the complexity class P.

5. A generalization of P class can be:
a) PTIME
b) DTIME
c) NP
d) None of the mentioned
View Answer

Answer: c
Explanation: P is a specific case of NP class, which is the class of decidable problems decidable by a non deterministic turing machine that runs in polynomial time.

6. Which of the following options are correct with reference to P-complete problems?
a) used for the problems which are difficult to solve in limited space
b) every problem in P can be reduced to it using proper reductions
c) complete problem for complexity class P
d) all of the mentioned
View Answer

Answer: d
Explanation:
The notion of P-complete decision problems is useful in the analysis of:
i) which problems are tough to parallelize effectively
ii) which problems are difficult to solve in limited space

7. A problem X belongs to P complexity class if there exist ________ algorithm to solve that problem, such that the number of steps of the algorithms bounded by a polynomial in n, where n is the length of the input.
a) 1
b) 2
c) 3
d) all of the mentioned
View Answer

Answer: d
Explanation: A problem X belongs to P complexity class if there exist atleast 1 algorithm to solve that problem, such that the number of steps of the algorithms bounded by a polynomial in n, where n is the length of the input. Thus, all the options are correct.
advertisement

8. Which of the following is a P-complete type of problem?
a) Circuit Value problem
b) Linear programming
c) Context free grammar membership
d) All of the mentioned
View Answer

Answer: d
Explanation: Given a context free grammar and a string, can the string be generated by the grammar? Such problems fall in the category of P-complete.

9. State true or false?
Statement: Given a turing machine, an input for the machine, and a number T(unary), does that machine halt on that input within the first T-steps?
The given problem is P-complete.
a) true
b) false
View Answer

Answer: a
Explanation: If we can parallelize a general simulation of a sequential computer, then we will be able to parallelize any program that runs on that computer. If this problem is in NC, then so every other problem in P.
advertisement

10. In the above problem, if the input is binary, the class the problem belongs?
a) EXPSPACE
b) DLOGTIME
c) EXPTIME-complete
d) All of the mentioned
View Answer

Answer: c
Explanation: It is the set of all decision problems that have exponential run time i.e. solvable by deterministic turing machine in O(2p(n)) time, where p(n) is a polynomial function of n.

Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory for Interviews, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.