Monotone simulations of non-monotone proofs. (Q1872729): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+Sorting in \(c \log n\) parallel steps
@@ Property / cites work: Sorting in \(c \log n\) parallel steps / rank @@
+Normal rank
@@ Property / cites work @@
+Monotone Proofs of the Pigeon Hole Principle
@@ Property / cites work: Monotone Proofs of the Pigeon Hole Principle / rank @@
+Normal rank
@@ Property / cites work @@
+Q4828877
@@ Property / cites work: Q4828877 / rank @@
+Normal rank
@@ Property / cites work @@
+Polynomial size proofs of the propositional pigeonhole principle
+Normal rank
@@ Property / cites work @@
+On the computational content of intuitionistic propositional proofs
+Normal rank
@@ Property / cites work @@
+The relative efficiency of propositional proof systems
+Normal rank
@@ Property / cites work @@
+The intractability of resolution
@@ Property / cites work: The intractability of resolution / rank @@
+Normal rank
@@ Property / cites work @@
+Q4856172
@@ Property / cites work: Q4856172 / rank @@
+Normal rank
@@ Property / cites work @@
+Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
+Normal rank
@@ Property / cites work @@
+Lower bounds for resolution and cutting plane proofs and monotone computations
+Normal rank
@@ Property / cites work @@
+Q4934563
@@ Property / cites work: Q4934563 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3758729
@@ Property / cites work: Q3758729 / rank @@
+Normal rank
@@ Property / cites work @@
+Proof theory. 2nd ed
@@ Property / cites work: Proof theory. 2nd ed / rank @@
+Normal rank
@@ Property / cites work @@
+The gap between monotone and non-monotone circuit complexity is exponential
+Normal rank
@@ Property / cites work @@
+Short monotone formulae for the majority function
@@ Property / cites work: Short monotone formulae for the majority function / rank @@
+Normal rank
@@ Property / cites work @@
+Q3762226
@@ Property / cites work: Q3762226 / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/s0022-0000(02)00020-x
+Normal rank
@@ Property / OpenAlex ID @@
+W2158912767
@@ Property / OpenAlex ID: W2158912767 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:1872729