~/ 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/6d5f35e3-d1af-4fe7-892b-7485e9db3edc/flashcard utf-8 LF