scientific article; zbMATH DE number 1445296
From MaRDI portal
Recommendations
- Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
- Automata, Languages and Programming
- Exponential bounds for DPLL below the satisfiability threshold
- Exponential lower bounds for DPLL algorithms on satisfiable random 3-CNF formulas
- The efficiency of resolution and Davis-Putnam procedures
Cited in
(32)- On the complexity of resolution with bounded conjunctions
- Lower bound techniques for QBF expansion
- A combinatorial characterization of treelike resolution space
- Proof complexity of modal resolution
- Space characterizations of complexity measures and size-space trade-offs in propositional proof systems
- Finding kernels or solving SAT
- A lower bound for the pigeonhole principle in tree-like resolution by asymmetric prover-delayer games
- Time-space trade-offs in resolution: superpolynomial lower bounds for superlinear space
- Strong ETH and resolution via games and the multiplicity of strategies
- Efficient reduction of nondeterministic automata with application to language inclusion testing
- Parameterized complexity of DPLL search procedures
- MaxSAT Resolution and Subcube Sums
- On (simple) decision tree rank
- Resolution with counting: dag-like lower bounds and different moduli
- Resolution lower bounds for perfect matching principles
- scientific article; zbMATH DE number 7471677 (Why is no real title available?)
- A characterization of tree-like resolution size
- A game characterisation of tree-like Q-resolution size
- Disproof of the neighborhood conjecture with implications to SAT
- Reversible pebble games and the relation between tree-like and general resolution space
- Clique problem, cutting plane proofs and communication complexity
- Advice complexity of adaptive priority algorithms
- Resolution over linear equations modulo two
- Improving resolution width lower bounds for k-CNFs with applications to the strong exponential time hypothesis
- Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
- scientific article; zbMATH DE number 7228403 (Why is no real title available?)
- Hard satisfiable instances for DPLL-type algorithms
- A game characterisation of tree-like Q-resolution size
- Size, cost and capacity: a semantic technique for hard random QBFs
- The depth of resolution proofs
- A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
- scientific article; zbMATH DE number 7029312 (Why is no real title available?)
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4952609)
