MCSP is hard for read-once nondeterministic branching programs
From MaRDI portal
Publication:6164002
Cites work
- scientific article; zbMATH DE number 7561559 (Why is no real title available?)
- scientific article; zbMATH DE number 7650416 (Why is no real title available?)
- Circuit lower bounds for MCSP from local pseudorandom generators
- Circuit minimization problem
- On lower bounds for read-\(k\)-times branching programs
- On the (non) \(\mathsf{NP}\)-hardness of computing circuit complexity
- Satisfiable Tseitin formulas are hard for nondeterministic read-once branching programs
- Slightly superexponential parameterized problems
- The complexity of minimizing and learning OBDDs and FBDDs
- Weak lower bounds on resource-bounded compression imply strong separations of complexity classes
This page was built for publication: MCSP is hard for read-once nondeterministic branching programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6164002)