Publication:4218095

zbMath0911.03018MaRDI QIDQ4218095

Pavel Pudlák

Publication date: 2 March 1999

zbMATH Keywords

probabilistic algorithms; proof complexity; satisfiability of \(k\)-CNF formulas

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

03B25: Decidability of theories and sets of sentences

03D15: Complexity of computation (including implicit computational complexity)

03F25: Relative consistency and interpretations

Related Items

Satisfiability Algorithm for Syntactic Read-$k$-times Branching Programs, A satisfiability algorithm and average-case hardness for formulas over the full binary basis