On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution (Q3012839): Difference between revisions

@@ Property / author @@
-Alexander A. Razborov
@@ Property / author: Alexander A. Razborov / rank @@
-Normal rank
@@ Property / author @@
+Alexander A. Razborov
@@ Property / author: Alexander A. Razborov / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1007/978-3-642-22006-7_54
+Normal rank
@@ Property / OpenAlex ID @@
+W2125291897
@@ Property / OpenAlex ID: W2125291897 / rank @@
+Normal rank
@@ Property / cites work @@
+Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas
+Normal rank
@@ Property / cites work @@
+Lower bounds for k-DNF resolution on random 3-CNFs
+Normal rank
@@ Property / cites work @@
+Space Complexity in Propositional Calculus
@@ Property / cites work: Space Complexity in Propositional Calculus / rank @@
+Normal rank
@@ Property / cites work @@
+On the automatizability of resolution and related propositional proof systems
+Normal rank
@@ Property / cites work @@
+Lower bounds for the weak pigeonhole principle and random formulas beyond resolution
+Normal rank
@@ Property / cites work @@
+Q2743691
@@ Property / cites work: Q2743691 / rank @@
+Normal rank
@@ Property / cites work @@
+Space complexity of random formulae in resolution
@@ Property / cites work: Space complexity of random formulae in resolution / rank @@
+Normal rank
@@ Property / cites work @@
+Short proofs are narrow—resolution made simple
@@ Property / cites work: Short proofs are narrow—resolution made simple / rank @@
+Normal rank
@@ Property / cites work @@
+Many hard examples for resolution
@@ Property / cites work: Many hard examples for resolution / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of resolution with bounded conjunctions
+Normal rank
@@ Property / cites work @@
+On the weak pigeonhole principle
@@ Property / cites work: On the weak pigeonhole principle / rank @@
+Normal rank
@@ Property / cites work @@
+Narrow Proofs May Be Spacious:Separating Space and Width in Resolution
+Normal rank
@@ Property / cites work @@
+Q5302095
@@ Property / cites work: Q5302095 / rank @@
+Normal rank
@@ Property / cites work @@
+Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
+Normal rank
@@ Property / cites work @@
+Exponential separation between Res(\(k\)) and Res(\(k+1\)) for \(k \leqslant \varepsilon\log n\)
+Normal rank
@@ Property / cites work @@
+A Switching Lemma for Small Restrictions and Lower Bounds for <i>k</i>-DNF Resolution
+Normal rank