Optimal proof systems imply complete sets for promise classes (Q1398371): Difference between revisions

@@ Property / cites work @@
+Q4039803
@@ Property / cites work: Q4039803 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3996675
@@ Property / cites work: Q3996675 / rank @@
+Normal rank
@@ Property / cites work @@
+Tally languages and complexity classes
@@ Property / cites work: Tally languages and complexity classes / rank @@
+Normal rank
@@ Property / cites work @@
+Q4835660
@@ Property / cites work: Q4835660 / rank @@
+Normal rank
@@ Property / cites work @@
+A uniform approach to define complexity classes
@@ Property / cites work: A uniform approach to define complexity classes / rank @@
+Normal rank
@@ Property / cites work @@
+Q4501551
@@ Property / cites work: Q4501551 / rank @@
+Normal rank
@@ Property / cites work @@
+On the power of parity polynomial time
@@ Property / cites work: On the power of parity polynomial time / rank @@
+Normal rank
@@ Property / cites work @@
+Universal classes of hash functions
@@ Property / cites work: Universal classes of hash functions / rank @@
+Normal rank
@@ Property / cites work @@
+Q4152212
@@ Property / cites work: Q4152212 / rank @@
+Normal rank
@@ Property / cites work @@
+The relative efficiency of propositional proof systems
+Normal rank
@@ Property / cites work @@
+Sparse sets in NP-P: EXPTIME versus NEXPTIME
@@ Property / cites work: Sparse sets in NP-P: EXPTIME versus NEXPTIME / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity classes without machines: on complete languages for UP
+Normal rank
@@ Property / cites work @@
+Q4258579
@@ Property / cites work: Q4258579 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3676130
@@ Property / cites work: Q3676130 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4856172
@@ Property / cites work: Q4856172 / rank @@
+Normal rank
@@ Property / cites work @@
+Propositional proof systems, the consistency of first order theories and the complexity of computations
+Normal rank
@@ Property / cites work @@
+Q4381398
@@ Property / cites work: Q4381398 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3755452
@@ Property / cites work: Q3755452 / rank @@
+Normal rank
@@ Property / cites work @@
+On an optimal quantified propositional proof system nal proof system and a complete language for NP ∩ co-NP for NP ∩ co-NP
+Normal rank
@@ Property / cites work @@
+On Approximation Algorithms for # P
@@ Property / cites work: On Approximation Algorithms for # P / rank @@
+Normal rank
@@ Property / cites work @@
+The Complexity of Propositional                                                   Proofs
@@ Property / cites work: The Complexity of Propositional Proofs / rank @@
+Normal rank
@@ Property / cites work @@
+RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS
+Normal rank