Start learning →

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.
Practise this question with Quill — GATE CSE →

Keep practising Algorithms

Browse all Algorithms questions for GATE CSE, or explore more Computer Science topics.

Start a Algorithms lesson →
Related questions
Sorting and searching bingoKnock out the true statementsWhich ones belongSpot the false statementDoes it need sorting firstWhich one does not belongSelection or insertionOne word is wrong