Question

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

The question was asked during an interview.

This is a very interesting question from Problem Solvable in Polynomial Time topic in section Intractable Problems of Automata Theory

Answer 1

The correct answer is:

(d) Deterministic Turing machine

Explanation: The complexity class P consists of all decision problems (problems with yes/no answers) that can be solved by a deterministic Turing machine in polynomial time. In other words, these are the problems for which an algorithm exists that can solve the problem in time proportional to a polynomial function of the input size.

• Push Down Automata (PDA): Typically used for context-free languages, but it is not used to define P.
• DFA (Deterministic Finite Automaton): Used for regular languages, but not for problems in class P.
• NDFA (Nondeterministic DFA): Also related to regular languages, not for defining P.

Thus, the correct definition of P is based on problems solvable by a deterministic Turing machine within polynomial time.