Generalized theorems on relationships among reducibility notions to certain complexity classes (Q4298368): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+A relationship between difference hierarchies and relativized polynomial hierarchies
+Normal rank
@@ Property / cites work @@
+Counting classes: Thresholds, parity, mods, and fewness
+Normal rank
@@ Property / cites work @@
+Probabilistic polynomial time is closed under parity reductions
+Normal rank
@@ Property / cites work @@
+PP is closed under intersection
@@ Property / cites work: PP is closed under intersection / 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 @@
+The complexity of theorem-proving procedures
@@ Property / cites work: The complexity of theorem-proving procedures / rank @@
+Normal rank
@@ Property / cites work @@
+PP is closed under truth-table reductions
@@ Property / cites work: PP is closed under truth-table reductions / rank @@
+Normal rank
@@ Property / cites work @@
+Computational Complexity of Probabilistic Turing Machines
+Normal rank
@@ Property / cites work @@
+On the power of deterministic reductions to C=P
@@ Property / cites work: On the power of deterministic reductions to C=P / rank @@
+Normal rank
@@ Property / cites work @@
+The strong exponential hierarchy collapses
@@ Property / cites work: The strong exponential hierarchy collapses / rank @@
+Normal rank
@@ Property / cites work @@
+The difference and truth-table hierarchies for NP
@@ Property / cites work: The difference and truth-table hierarchies for NP / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of optimization problems
@@ Property / cites work: The complexity of optimization problems / rank @@
+Normal rank
@@ Property / cites work @@
+Relativization of questions about log space computability
+Normal rank
@@ Property / cites work @@
+A comparison of polynomial time reducibilities
@@ Property / cites work: A comparison of polynomial time reducibilities / rank @@
+Normal rank
@@ Property / cites work @@
+A complexity theory for feasible closure properties
+Normal rank
@@ Property / cites work @@
+Reductions on NP and p-selective sets
@@ Property / cites work: Reductions on NP and p-selective sets / rank @@
+Normal rank
@@ Property / cites work @@
+Q4035673
@@ Property / cites work: Q4035673 / rank @@
+Normal rank
@@ Property / cites work @@
+Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
+Normal rank
@@ Property / cites work @@
+The complexity of computing the permanent
@@ Property / cites work: The complexity of computing the permanent / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of combinatorial problems with succinct input representation
+Normal rank
@@ Property / cites work @@
+More complicated questions about maxima and minima, and some closures of NP
+Normal rank