scientific article; zbMATH DE number 1445296
From MaRDI portal
Publication:4952609
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
(37)- A combinatorial characterization of treelike resolution space
- A lower bound for the pigeonhole principle in tree-like resolution by asymmetric prover-delayer games
- Resolution lower bounds for perfect matching principles
- On the complexity of resolution with bounded conjunctions
- Lower bound techniques for QBF expansion
- Resolution with counting: dag-like lower bounds and different moduli
- Reversible pebble games and the relation between tree-like and general resolution space
- Resolution over linear equations modulo two
- Strong ETH and resolution via games and the multiplicity of strategies
- A game characterisation of tree-like Q-resolution size
- A characterization of tree-like resolution size
- Hard satisfiable instances for DPLL-type algorithms
- A game characterisation of tree-like Q-resolution size
- Time-space trade-offs in resolution: superpolynomial lower bounds for superlinear space
- scientific article; zbMATH DE number 7228403 (Why is no real title available?)
- Disproof of the neighborhood conjecture with implications to SAT
- Finding kernels or solving SAT
- Clique problem, cutting plane proofs and communication complexity
- Efficient reduction of nondeterministic automata with application to language inclusion testing
- scientific article; zbMATH DE number 7029312 (Why is no real title available?)
- A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution
- Size, cost and capacity: a semantic technique for hard random QBFs
- A separator theorem for hypergraphs and a CSP-SAT algorithm
- MaxSAT Resolution and Subcube Sums
- Parameterized complexity of DPLL search procedures
- On (simple) decision tree rank
- Space characterizations of complexity measures and size-space trade-offs in propositional proof systems
- Advice complexity of adaptive priority algorithms
- The depth of resolution proofs
- A simple supercritical tradeoff between size and height in resolution
- Lower bounds for regular resolution over parities
- Resolution over linear equations: combinatorial games for tree-like size and space
- Supercritical size-width tree-like resolution trade-offs for graph isomorphism
- Lifting to randomized parity decision trees
- Proof complexity of modal resolution
- Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
- Improving resolution width lower bounds for k-CNFs with applications to the strong exponential time hypothesis
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)
