Propositional proofs and reductions between NP search problems (Q435190): Difference between revisions

@@ Property / cites work @@
+The relative complexity of NP search problems
@@ Property / cites work: The relative complexity of NP search problems / rank @@
+Normal rank
@@ Property / cites work @@
+Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
+Normal rank
@@ Property / cites work @@
+An exponential separation between the parity principle and the pigeonhole principle
+Normal rank
@@ Property / cites work @@
+Separation results for the size of constant-depth propositional proofs
+Normal rank
@@ Property / cites work @@
+Corrected upper bounds for free-cut elimination
@@ Property / cites work: Corrected upper bounds for free-cut elimination / rank @@
+Normal rank
@@ Property / cites work @@
+Q4375786
@@ Property / cites work: Q4375786 / rank @@
+Normal rank
@@ Property / cites work @@
+Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
+Normal rank
@@ Property / cites work @@
+An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
+Normal rank
@@ Property / cites work @@
+Q4228469
@@ Property / cites work: Q4228469 / rank @@
+Normal rank
@@ Property / cites work @@
+A tight relationship between generic oracles and type-2 complexity theory
+Normal rank
@@ Property / cites work @@
+The complexity of computing a Nash equilibrium
@@ Property / cites work: The complexity of computing a Nash equilibrium / rank @@
+Normal rank
@@ Property / cites work @@
+Herbrandizing search problems in Bounded Arithmetic
+Normal rank
@@ Property / cites work @@
+How easy is local search?
@@ Property / cites work: How easy is local search? / rank @@
+Normal rank
@@ Property / cites work @@
+Q4856172
@@ Property / cites work: Q4856172 / rank @@
+Normal rank
@@ Property / cites work @@
+On total functions, existence theorems and computational complexity
+Normal rank
@@ Property / cites work @@
+On the complexity of the parity argument and other inefficient proofs of existence
+Normal rank