The theory of the polynomial many-one degrees of recursive sets is undecidable (Q5096783): Difference between revisions

@@ Property / full work available at URL @@
+https://doi.org/10.1007/3-540-55210-3_185
+Normal rank
@@ Property / OpenAlex ID @@
+W1599138491
@@ Property / OpenAlex ID: W1599138491 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3337458
@@ Property / cites work: Q3337458 / rank @@
+Normal rank
@@ Property / cites work @@
+Sublattices of the polynomial time degrees
@@ Property / cites work: Sublattices of the polynomial time degrees / rank @@
+Normal rank
@@ Property / cites work @@
+An Inhomogeneity in the Structure of Karp Degrees
@@ Property / cites work: An Inhomogeneity in the Structure of Karp Degrees / rank @@
+Normal rank
@@ Property / cites work @@
+Q3778006
@@ Property / cites work: Q3778006 / rank @@
+Normal rank
@@ Property / cites work @@
+The theory of the recursively enumerable weak truth-table degrees is undecidable
+Normal rank
@@ Property / cites work @@
+Honest polynomial time reducibilities and the \(P=?NP\) problem
+Normal rank
@@ Property / cites work @@
+Decidability and Boolean representations
@@ Property / cites work: Decidability and Boolean representations / 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 @@
+The structure of the honest polynomial m-degrees
@@ Property / cites work: The structure of the honest polynomial m-degrees / rank @@
+Normal rank
@@ Property / cites work @@
+Q3665086
@@ Property / cites work: Q3665086 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3734391
@@ Property / cites work: Q3734391 / rank @@
+Normal rank
@@ Property / cites work @@
+Reducibility among Combinatorial Problems
@@ Property / cites work: Reducibility among Combinatorial Problems / rank @@
+Normal rank
@@ Property / cites work @@
+On the Structure of Polynomial Time Reducibility
@@ Property / cites work: On the Structure of Polynomial Time Reducibility / rank @@
+Normal rank
@@ Property / cites work @@
+On the structure of sets in NP and other complexity classes
+Normal rank
@@ Property / cites work @@
+Polynomial and abstract subrecursive classes
@@ Property / cites work: Polynomial and abstract subrecursive classes / rank @@
+Normal rank
@@ Property / cites work @@
+On the theory of the PTIME degrees of the recursive sets
+Normal rank
@@ Property / cites work @@
+The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory
+Normal rank