PyQdeck LogoPyQdeckSubjectsSyllabusBlog
Back to the 2025 paper

Module 4: Tractable and Intractable Problems

20252m

Which complexity class contains problems for which a given solution can be verified in polynomial time by a deterministic Turing machine?

(i) Class P
(ii) Class NP
(iii) Class NP-Hard
(iv) Class Undecidable

Search GoogleAsk AI
Worked SolutionAI Assisted

Answer: (ii) Class NP

Explanation:

  • P: problems solvable in polynomial time by a deterministic TM.
  • NP: problems where a proposed solution (certificate) can be verified in polynomial time by a deterministic TM (equivalently, solvable in polynomial time by a non-deterministic TM). P⊆NPP \subseteq NP.
  • NP-Hard: at least as hard as any NP problem (every NP problem reduces to it); may not be in NP.
  • NP-Complete = NP ∩\cap NP-Hard.
  • Undecidable: no TM can solve all instances.

The definition "verifiable in polynomial time by deterministic TM" is exactly NP.

Correct choice: (ii) Class NP

Similar questions

Design and Analysis of Algorithms What is the relationship between NP and P complexity classes? (i) P is a subset of NP (ii) NP is a subset of P (iii) P and NP are equivalent (iv) P and NP are disjoint sets20232mDesign and Analysis of Algorithms The Quantified Boolean Formula problem is a canonical complete problem for which of the following complexity classes? (i) NP (ii) P (iii) PSPACE (iv) co-NP20252mDesign & Analysis of AlgorithmsHamiltonian path problem is ______? - (i) NP Problem - (ii) NP Complete - (iii) P Class Problem - (iv) N Class Problem20242mDesign & Analysis of AlgorithmsThe choice of polynomial class has led to the development of an extensive theory called: - (i) computational complexity - (ii) time complexity - (iii) problem complexity - (iv) decision complexity20222m
PreviousIf all edge weights in a graph are positive, what is the minimum number of edges in a spanning tree for a graph with vertices? (i) V (ii) V-1 (iii) V+1 (iv) 2VNextWhat is the approximation ratio (or performance ratio) of the greedy algorithm for the Vertex Cover problem? (i) 2 (ii) 1.5 (iii) ln n (iv) 1
AI LearningWeb Platform

Coursify — Personal AI Course Generator

Struggling with a difficult subject or concept? Turn any engineering topic into a structured course with interactive lessons, quizzes, and research-backed explanations.

Try Coursify Free