Extended Frege proofs, circuits and rewriting

Jan Krajicek

Inspired by a statement about Extended Frege proof systems by Jain and Jin (FOCS 2022) we prove that: - there is a p-time binary relation $\approx$ between circuits that implies th…