~/ learn/ comp-372/ cards/ P, NP, and verification
1 of 5

Define the complexity class P.

Define the complexity class P.

Answer

P = the set of decision problems (languages) decidable by a polynomial-time algorithm, i.e. in O(n^k) time for some constant k.

P formalizes "tractable": some single algorithm answers yes/no in time bounded by a fixed polynomial in the input size n.

space flip · ← → navigate · esc to exit
NORMAL ~/memra/library/0f68ef17-ec20-42df-8554-d78c2a757f27/flashcard utf-8 LF