Besides P and NP, several other classes will be used in this book. Given a decision problem P = L P ,Y P , the complementary problem of P is defined as P = L P ,L P \ Y P . Given a complexity class C, a decision problem belongs to the class coC if P belongs to C. Notably, coNP is the class of all decision problems whose complement is in NP. For instance, deciding that a directed graph does not possess a Hamiltonian cycle is in coNP (and coNP-complete).