scientific article; zbMATH DE number 1445296
From MaRDI portal
zbMATH Open0953.68150MaRDI QIDQ4952609FDOQ4952609
Authors: Pavel Pudlák, Russell Impagliazzo 
Publication date: 10 May 2000
Title of this publication is not available (Why is that?)
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
Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Graph theory (05C99)
Cited In (32)
- On the complexity of resolution with bounded conjunctions
- Lower bound techniques for QBF expansion
- A combinatorial characterization of treelike resolution space
- Space characterizations of complexity measures and size-space trade-offs in propositional proof systems
- Proof complexity of modal resolution
- Finding kernels or solving SAT
- Time-space trade-offs in resolution: superpolynomial lower bounds for superlinear space
- A lower bound for the pigeonhole principle in tree-like resolution by asymmetric prover-delayer games
- Efficient reduction of nondeterministic automata with application to language inclusion testing
- Strong ETH and resolution via games and the multiplicity of strategies
- 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
- Title not available (Why is that?)
- Resolution lower bounds for perfect matching principles
- A characterization of tree-like resolution size
- A game characterisation of tree-like Q-resolution size
- Advice complexity of adaptive priority algorithms
- 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
- 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
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
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)
