Skip to main content
Source Link
Kaveh
  • 22.2k
  • 8
  • 87
  • 187

There are hierarchies in propositional proof complexity similar to those in circuit complexity. E.g. $G_i$ propositional roof systems are similar to $\mathsf{PH}$, C-Frege proof systems for $C \subset \mathsf{P}$ are similar to circuit complexity classes $C$, and so on.

There are also hierarchies in bounded arithmetics, e.g. $\mathsf{S^i_j}$ theories, etc.

Post Made Community Wiki by Kaveh