Automating OBDD proofs is NP-hard

DOI10.4230/LIPICS.MFCS.2022.59MaRDI QIDQ6584062zbMATH OpenFDO

Authors Dmitry Itsykson, Artur Riazanov

Publication date 6 August 2024

Full work available at URL https://doi.org/10.4230/LIPICS.MFCS.2022.59

zbMATH Keywords

automatabilitydag-like communicationliftingOBDDproof complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited in

(3)

• Quantum automating TC^0-Frege is LWE-hard
• Quantum automating \(\mathrm{TC}^0\)-Frege is LWE-hard
• Prover-adversary games for systems over (non-deterministic) branching programs

This page was built for publication: Automating OBDD proofs is NP-hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6584062)