MCSP is hard for read-once nondeterministic branching programs
From MaRDI portal
Publication:6164002
DOI10.1007/978-3-031-20624-5_38MaRDI QIDQ6164002
Artur Riazanov, Ludmila Glinskih
Publication date: 26 July 2023
Published in: LATIN 2022: Theoretical Informatics (Search for Journal in Brave)
Algorithms in computer science (68Wxx) Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of minimizing and learning OBDDs and FBDDs
- On lower bounds for read-\(k\)-times branching programs
- Circuit minimization problem
- Satisfiable Tseitin Formulas Are Hard for Nondeterministic Read-Once Branching Programs.
- Weak lower bounds on resource-bounded compression imply strong separations of complexity classes
- Slightly Superexponential Parameterized Problems
This page was built for publication: MCSP is hard for read-once nondeterministic branching programs
