ACtE07 · Chapter 7Theory of Computation & Graphics🏛️ Past Licensure QuestionID: a15dceda
In computational complexity theory, the complexity class P consists of all decision problems that can be solved in polynomial time by a:
In computational complexity theory, the complexity class P consists of all decision problems that can be solved in polynomial time by a:
Multiple Choice Options
- A
Deterministic Finite Automaton (DFA)
- B
Non-Deterministic Turing Machine (NTM)
- C✓ Correct Option
Deterministic Turing Machine (DTM)
- D
Pushdown Automaton (PDA)
Detailed Technical Solution & Explanation
By definition, the class is the set of all decision problems solvable by a Deterministic Turing Machine in polynomial time ( for some constant ). In contrast, is solvable by a Non-Deterministic Turing Machine in polynomial time.
Option Analysis:
•
Option A (Deterministic Finite Automaton (DFA)): Recognizes regular languages, not general polynomial-time computable problems.
•
Option B (Non-Deterministic Turing Machine (NTM)): Defines the class , not .
•
Option C (Deterministic Turing Machine (DTM)): Correct. Standard formal foundation for class .
•
Option D (Pushdown Automaton (PDA)): Recognizes context-free languages.
Reference: Demo2 · Set 2NEC Licensure Syllabus