Do there exist complete sets for promise classes? (Q3107337): Difference between revisions

@@ Property / cites work @@
+Q4039803
@@ Property / cites work: Q4039803 / rank @@
+Normal rank
@@ Property / cites work @@
+Classes of representable disjoint \textsf{NP}-pairs
+Normal rank
@@ Property / cites work @@
+Tuples of disjoint \(\mathsf{NP}\)-sets
@@ Property / cites work: Tuples of disjoint \(\mathsf{NP}\)-sets / rank @@
+Normal rank
@@ Property / cites work @@
+Proof systems that take advice
@@ Property / cites work: Proof systems that take advice / rank @@
+Normal rank
@@ Property / cites work @@
+Nondeterministic functions and the existence of optimal proof systems
+Normal rank
@@ Property / cites work @@
+A tight Karp-Lipton collapse result in bounded arithmetic
+Normal rank
@@ Property / cites work @@
+Consequences of the provability of <i>NP</i> ⊆ <i>P</i>/<i>poly</i>
+Normal rank
@@ Property / cites work @@
+The relative efficiency of propositional proof systems
+Normal rank
@@ Property / cites work @@
+Reductions between disjoint NP-pairs
@@ Property / cites work: Reductions between disjoint NP-pairs / rank @@
+Normal rank
@@ Property / cites work @@
+Disjoint NP-Pairs
@@ Property / cites work: Disjoint NP-Pairs / rank @@
+Normal rank
@@ Property / cites work @@
+Canonical disjoint NP-pairs of propositional proof systems
+Normal rank
@@ Property / cites work @@
+Complexity classes without machines: on complete languages for UP
+Normal rank
@@ Property / cites work @@
+\(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP
+Normal rank
@@ Property / cites work @@
+Optimal proof systems imply complete sets for promise classes
+Normal rank
@@ Property / cites work @@
+Propositional proof systems, the consistency of first order theories and the complexity of computations
+Normal rank
@@ Property / cites work @@
+Some consequences of cryptographical conjectures for \(S_2^1\) and EF
+Normal rank
@@ Property / cites work @@
+On Circuit-Size Complexity and the Low Hierarchy in NP
+Normal rank
@@ Property / cites work @@
+Q4273947
@@ Property / cites work: Q4273947 / rank @@
+Normal rank
@@ Property / cites work @@
+On an optimal propositional proof system and the structure of easy subsets of TAUT.
+Normal rank
@@ Property / cites work @@
+A low and a high hierarchy within NP
@@ Property / cites work: A low and a high hierarchy within NP / rank @@
+Normal rank
@@ Property / cites work @@
+A taxonomy of complexity classes of functions
@@ Property / cites work: A taxonomy of complexity classes of functions / rank @@
+Normal rank