Which set inclusion is established (i.e., proven, not open)?
ANP ⊆ P
BP ⊆ NP
CP = NP
DP and NP are disjoint
Answer & Solution
Correct answer: B. P ⊆ NP
Every problem in P trivially has a polynomial verifier (the polynomial-time solver IS the verifier; ignore the certificate). So P ⊆ NP is straightforwardly proven. Whether the reverse inclusion holds (giving P = NP) is the famous open question; the two are NOT proven equal and they are NOT disjoint either.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined forThe running time and space of Floyd-Warshall on a graph with V vertices and E edges is