Computational Complexity HT25, Index of problems and reductions

• NP
• NL
• PSPACE
• P
• The polynomial hierarchy

• [[Course - Computational Complexity HT25]]^U
  • [[Notes - Computational Complexity HT25, Common proof themes]]^U
  • See also:
  • [[Course - Algorithms and Data Structures HT24]]^U

This page collects some of the languages considered in the courses [[Course - Algorithms and Data Structures HT24]]^U and [[Course - Computational Complexity HT25]]^U, along with some of the reductions between them and proofs of their completeness.

NP

• [[Notes - Computational Complexity HT25, Cook-Levin theorem]]^U
  • $\mathbf{SAT}$
  • $\mathbf{CircuitSAT}$
  • Proof that $\mathbf{SAT}$ is $\mathsf{NP}$-complete by associating tableaus with formulas (uses the tableau idea)
  • Proof $\mathbf{CircuitSAT}$ is $\mathsf{NP}$-complete by appealing to $\mathsf P \subseteq \mathsf P _ {/\mathsf{poly} }$ (uses the tableau idea)
  • $\mathbf{SAT} \le \mathbf{3SAT}$
  • $\mathbf{3SAT} \le \mathbf{CircuitSAT}$
• [[Notes - ADS HT24, NP-hardness and NP-completeness]]^U
  • $\mathbf{IndependentSet}$
  • $\mathbf{3SAT}$
  • $\mathbf{DominatingSet}$
  • $\mathbf{VertexCover}$
  • $\mathbf{LargeCut}$
  • $\mathbf{HamiltonianCycle}$
  • $\mathbf{3COL}$
  • $\mathbf{SetCover}$
  • $\mathbf{HittingSet}$
  • $\mathbf{SubsetSum}$
  • $\mathbf{EqualPartition}$
  • $\mathbf{DisjointTriangles}$
  • $\mathbf{LongPath}$
  • $\mathbf{ILP}$
  • $\mathbf{LineCover}$
  • $\mathbf{VertexCover} \le \mathbf{IndependentSet}$
  • $\mathbf{IndependentSet} \le \mathbf{Clique}$
  • $\mathbf{3SAT} \le \mathbf{VertexCover}$
  • $\mathbf{SubsetSum} \le \mathbf{EqualPartition}$
  • $\mathbf{3SAT} \le \mathbf{ILP}$
  • $\mathbf{3SAT} \le \mathbf{SubsetSum}$
• [[Notes - Computational Complexity HT25, Nondeterminism]]^U
  • $\mathbf{3SAT} \le \mathbf{Clique}$
• Other examples:
  • $\mathbf{VertexCover} \le \mathbf{TriangleFreeDominatingSet}$ (in 2021 complexity exam)
  • Show that the problem of determining the minimum number of edge additions / deletions so that $G’$ is triangle free (question 1 in 2022 complexity exam)
  • $\mathbf{Pattern}$ (question 3 in 2022 complexity exam)
  • $\mathbf{3COL}$
  • $\mathbf{3SAT} \le \mathbf{3COL}$ (https://www.cs.toronto.edu/~lalla/373s16/notes/3col.pdf)

NL

NL-hardness and NL-completeness is defined with respect to logarithmic-space reductions rather than polynomial-time ones (all nontrivial languages in NL are complete with respect to polynomial-time ones).

• [[Notes - Computational Complexity HT25, Sublinear space classes]]^U
  • $\mathbf{PATH}$ (i.e. $\mathbf{REACH}$, $\mathbf{STCON}$)
  • Proof $\mathbf{PATH}$ is NL-complete (search through the configuration space of a TM)
• Other examples:
  • $\mathbf{SCOP}$ (“strongly connected graphs with overlapping paths”) is NL-complete (in 2021 complexity exam)

PSPACE

PSPACE-hardness and PSPACE-completeness is defined with respect to polynomial-time reductions.

• [[Notes - Computational Complexity HT25, PSPACE-completeness]]^U
  • $\mathbf{TQBF}$
  • Proof $\mathbf{TQBF}$ is $\mathsf{PSPACE}$-complete (uses the “meet-in-the-middle” trick to find a reasonably-sized totally quantified boolean formula representing whether a TM accepts, and in fact this reduction is also logarithmic-space)

P

P-hardness and P-completeness is defined with respect to logarithmic-space reductions.

• [[Notes - Computational Complexity HT25, Boolean circuits]]^U
  • $\mathbf{CVP}$ (“circuit value problem”)
  • Proof $\mathbf{CVP}$ is $\mathsf P$-complete (uses the result that $\mathsf P \subseteq \mathsf P _ {/\mathsf{poly} })$.

The polynomial hierarchy

• [[Notes - Computational Complexity HT25, Polynomial hierarchy]]^U
  • $\Sigma^p _ i$, has complete problem $\Sigma^p _ i\mathsf{SAT}$
  • $\Pi^p _ i$, has complete problem $\Pi^p _ i\mathsf{SAT}$