TheoComp

Decision problems solvable by a deterministic Turing machine in polynomial time.

Decision problems whose yes-instances can be verified in polynomial time by a deterministic Turing machine (equivalently, solvable in polynomial time by a nondeterministic Turing machine).

Decision problems whose no-instances are solvable by a deterministic Turing machine in polynomial time (i.e., complements of problems in P).
Note: Since P is closed under complement, co-P = P.

Decision problems whose no-instances can be verified in polynomial time (complements of problems in NP).

Problems in NP that are at least as hard as every problem in NP:

1. Membership: They themselves lie in NP.

2. Hardness: Every NP problem reduces to them via a polynomial-time many-to-one reduction.
   If any NP-complete problem is solved in polynomial time, P = NP.

Problems at least as hard as the hardest problems in NP (every NP problem reduces to them), but not required to be in NP; they may be decision, optimization, or even non-decidable problems.

co-P is the class of decision problems whose complements are solvable by a deterministic Turing machine in polynomial time:

A straightforward “brute-force’’ procedure tries every possible colouring of the n vertices with two colours and checks whether any of them respects all m edges. That requires examining 2ⁿ assignments, each verified in O(n + m) time, for a worst-case running time Θ(2ⁿ · (n + m)), which is exponential—not polynomial—in the input size.

The fact that 2-COLOR is in P comes from a different algorithm (e.g. a single BFS/DFS per connected component to test bipartiteness) that runs in O(n + m) time. Thus membership in P guarantees the existence of a polynomial-time algorithm, but the naïve brute-force method is not one of them.