An exponential separation between the parity principle and the pigeonhole principle (Q1923563): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of the pigeonhole principle
@@ Property / cites work: The complexity of the pigeonhole principle / rank @@
+Normal rank
@@ Property / cites work @@
+Q4035300
@@ Property / cites work: Q4035300 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4234077
@@ Property / cites work: Q4234077 / rank @@
+Normal rank
@@ Property / cites work @@
+Optimal bounds for decision problems on the CRCW PRAM
+Normal rank
@@ Property / cites work @@
+An exponential separation between the parity principle and the pigeonhole principle
+Normal rank
@@ Property / cites work @@
+Q3794177
@@ Property / cites work: Q3794177 / rank @@
+Normal rank
@@ Property / cites work @@
+Polynomial size proofs of the propositional pigeonhole principle
+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 @@
+An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
+Normal rank
@@ Property / cites work @@
+Q4027186
@@ Property / cites work: Q4027186 / rank @@
+Normal rank
@@ Property / cites work @@
+Exponential lower bounds for the pigeonhole principle
+Normal rank
@@ Property / cites work @@
+Q3689182
@@ Property / cites work: Q3689182 / rank @@
+Normal rank
@@ Property / cites work @@
+Hard examples for resolution
@@ Property / cites work: Hard examples for resolution / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:1923563