NP-Complete, Cook-Levin Theorem, and coNP

owo a chart!

Properties of NP Completeness

for \(NP\) complete \(A\), \(B\), is \(A\ \text{op}\ B\) np complete?

Properties of P and NP

for \(P\) or \(NP\) \(A\), \(B\), is \(A\ \text{op}\ B\) np complete?

Oracle Polynomial Time, Space Complexity, Approximation Algorithms and PCP Theorem

Key Sequence

Notation

New Concepts

Important Results / Claims

Questions

Interesting Factoids

“regularization”: removing columns (i.e. explicitly making things roughly degenerate to fit more generally)

“tall full-rank matrix” (i.e. let \(A\) be \(m \times n\), such that \(m \geq n\)).

Solving such full-rank linear systems—

\begin{equation} Ac = b \implies U \Sigma V^{T} c = b \implies \Sigma \qty(V^{T}c) = U^{T} b \end{equation}

We can now solve this above by simply dividing by the nonzero singular values of each row (since we are full rank, this is true). The last equations are zero.