~/ learn/ comp-372/ cards/ Intractability: NP-Completeness
1 of 17

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/812d9ef5-9d85-4f9e-89e4-591bf5283d5e/flashcard utf-8 LF