scientific article; zbMATH DE number 1445296
From MaRDI portal
Publication:4952609
zbMath0953.68150MaRDI QIDQ4952609
Russell Impagliazzo, Pavel Pudlák
Publication date: 10 May 2000
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)
Related Items (30)
Resolution lower bounds for perfect matching principles ⋮ Proof complexity of modal resolution ⋮ On the complexity of resolution with bounded conjunctions ⋮ Unnamed Item ⋮ Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas ⋮ Strong ETH and resolution via games and the multiplicity of strategies ⋮ A lower bound for the pigeonhole principle in tree-like resolution by asymmetric prover-delayer games ⋮ On (simple) decision tree rank ⋮ Unnamed Item ⋮ Improving resolution width lower bounds for \(k\)-CNFs with applications to the strong exponential time hypothesis ⋮ A game characterisation of tree-like Q-resolution size ⋮ Finding kernels or solving SAT ⋮ 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 ⋮ Clique problem, cutting plane proofs and communication complexity ⋮ A characterization of tree-like resolution size ⋮ Unnamed Item ⋮ 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 ⋮ A Game Characterisation of Tree-like Q-resolution Size ⋮ Parameterized Complexity of DPLL Search Procedures ⋮ A combinatorial characterization of treelike resolution space ⋮ Time-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Resolution over linear equations modulo two ⋮ Hard satisfiable instances for DPLL-type algorithms ⋮ MaxSAT Resolution and Subcube Sums
This page was built for publication:
