Polynomial-time axioms of choice and polynomial-time cardinality (Q6109071): Difference between revisions

@@ Property / cites work @@
+The counting complexity of group-definable languages
+Normal rank
@@ Property / cites work @@
+Computable structures and the hyperarithmetical hierarchy
+Normal rank
@@ Property / cites work @@
+A second step toward the polynomial hierarchy
@@ Property / cites work: A second step toward the polynomial hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+On Isomorphisms and Density of $NP$ and Other Complete Sets
+Normal rank
@@ Property / cites work @@
+Q3334986
@@ Property / cites work: Q3334986 / rank @@
+Normal rank
@@ Property / cites work @@
+On truth-table reducibility to SAT
@@ Property / cites work: On truth-table reducibility to SAT / rank @@
+Normal rank
@@ Property / cites work @@
+Generalized Effective Reducibility
@@ Property / cites work: Generalized Effective Reducibility / rank @@
+Normal rank
@@ Property / cites work @@
+The recursive equivalence type of a class of sets
@@ Property / cites work: The recursive equivalence type of a class of sets / rank @@
+Normal rank
@@ Property / cites work @@
+Q5661491
@@ Property / cites work: Q5661491 / rank @@
+Normal rank
@@ Property / cites work @@
+Inverting onto functions.
@@ Property / cites work: Inverting onto functions. / rank @@
+Normal rank
@@ Property / cites work @@
+Every polynomial-time 1-degree collapses if and only if P = PSPACE
+Normal rank
@@ Property / cites work @@
+Complexity classes of equivalence problems revisited
+Normal rank
@@ Property / cites work @@
+Introduction to Autoreducibility and Mitoticity
@@ Property / cites work: Introduction to Autoreducibility and Mitoticity / rank @@
+Normal rank
@@ Property / cites work @@
+Autoreducibility, mitoticity, and immunity
@@ Property / cites work: Autoreducibility, mitoticity, and immunity / rank @@
+Normal rank
@@ Property / cites work @@
+Theory and Applications of Models of Computation
@@ Property / cites work: Theory and Applications of Models of Computation / rank @@
+Normal rank
@@ Property / cites work @@
+Splitting NP-Complete Sets
@@ Property / cites work: Splitting NP-Complete Sets / rank @@
+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 @@
+The complexity of unions of disjoint sets
@@ Property / cites work: The complexity of unions of disjoint sets / rank @@
+Normal rank
@@ Property / cites work @@
+Compression and Ranking
@@ Property / cites work: Compression and Ranking / rank @@
+Normal rank
@@ Property / cites work @@
+Scalability and the isomorphism problem
@@ Property / cites work: Scalability and the isomorphism problem / rank @@
+Normal rank
@@ Property / cites work @@
+Polynomial-time compression
@@ Property / cites work: Polynomial-time compression / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity Measures for Public-Key Cryptosystems
@@ Property / cites work: Complexity Measures for Public-Key Cryptosystems / rank @@
+Normal rank
@@ Property / cites work @@
+On sets polynomially enumerable by iteration
@@ Property / cites work: On sets polynomially enumerable by iteration / rank @@
+Normal rank
@@ Property / cites work @@
+\(p\)-Selective sets and reducing search to decision vs. self-reducibility
+Normal rank
@@ Property / cites work @@
+Theory of semi-feasible algorithms
@@ Property / cites work: Theory of semi-feasible algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Computing Solutions Uniquely Collapses the Polynomial Hierarchy
+Normal rank
@@ Property / cites work @@
+Q4350444
@@ Property / cites work: Q4350444 / rank @@
+Normal rank
@@ Property / cites work @@
+Axiom of choice
@@ Property / cites work: Axiom of choice / rank @@
+Normal rank
@@ Property / cites work @@
+Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
+Normal rank
@@ Property / cites work @@
+On some natural complete operators
@@ Property / cites work: On some natural complete operators / rank @@
+Normal rank
@@ Property / cites work @@
+Completeness, Approximation and Density
@@ Property / cites work: Completeness, Approximation and Density / rank @@
+Normal rank
@@ Property / cites work @@
+Collapsing degrees
@@ Property / cites work: Collapsing degrees / rank @@
+Normal rank
@@ Property / cites work @@
+The isomorphism conjecture fails relative to a random oracle
+Normal rank
@@ Property / cites work @@
+Category and Measure in Complexity Classes
@@ Property / cites work: Category and Measure in Complexity Classes / rank @@
+Normal rank
@@ Property / cites work @@
+Realizability and recursive set theory
@@ Property / cites work: Realizability and recursive set theory / rank @@
+Normal rank
@@ Property / cites work @@
+Computable Structure Theory
@@ Property / cites work: Computable Structure Theory / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity-theoretic algebra. II: Boolean algebras
+Normal rank
@@ Property / cites work @@
+Q3478393
@@ Property / cites work: Q3478393 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3484825
@@ Property / cites work: Q3484825 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3815528
@@ Property / cites work: Q3815528 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5337203
@@ Property / cites work: Q5337203 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4353856
@@ Property / cites work: Q4353856 / rank @@
+Normal rank
@@ Property / cites work @@
+Polynomial Time Enumeration Reducibility
@@ Property / cites work: Polynomial Time Enumeration Reducibility / rank @@
+Normal rank
@@ Property / cites work @@
+P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
+Normal rank
@@ Property / cites work @@
+Some observations on NP real numbers and P-selective sets
+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 @@
+Natural Self-Reducible Sets
@@ Property / cites work: Natural Self-Reducible Sets / rank @@
+Normal rank
@@ Property / cites work @@
+Q3998345
@@ Property / cites work: Q3998345 / 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
@@ Property / cites work @@
+Finite axioms of choice
@@ Property / cites work: Finite axioms of choice / rank @@
+Normal rank