Partial minimum branching program size problem is ETH-hard
From MaRDI portal
Cites work
- 3.1 n − o ( n ) circuit lower bounds for explicit functions
- A better-than-3n lower bound for the circuit complexity of an explicit function
- A direct-sum theorem for read-once branching programs
- A simplified NP-complete satisfiability problem
- Branching program size is almost linear in formula size
- Branching Programs and Binary Decision Diagrams
- Circuit lower bounds from NP-hardness of MCSP under turing reductions
- Circuit minimization problem
- Constant depth formula and partial function versions of MCSP are hard
- Exact minimization of binary decision diagrams using implicit techniques
- Finding the optimal variable ordering for binary decision diagrams
- Hardness of indentifying the minimum ordered binary decision diagram
- scientific article; zbMATH DE number 176876 (Why is no real title available?)
- scientific article; zbMATH DE number 7250145 (Why is no real title available?)
- Improving the variable ordering of OBDDs is NP-complete
- MCSP is hard for read-once nondeterministic branching programs
- Natural proofs
- NP-hardness of learning programs and partial MCSP
- On the (non) \(\mathsf{NP}\)-hardness of computing circuit complexity
- On the minimization of (complete) ordered binary decision diagrams
- On the synthesis of self-correcting schemes from functional elements with a small number of reliable elements
- Slightly superexponential parameterized problems
- The complexity of minimizing and learning OBDDs and FBDDs
- The minimum formula size problem is (ETH) hard
This page was built for publication: Partial minimum branching program size problem is ETH-hard
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7296693)
