Some remarks on witness functions for nonpolynomial and noncomplete sets in NP (Q1079364): Difference between revisions

@@ Property / Wikidata QID @@
+Q56610696
@@ Property / Wikidata QID: Q56610696 / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W2008585307
@@ Property / OpenAlex ID: W2008585307 / rank @@
+Normal rank
@@ Property / cites work @@
+On Isomorphisms and Density of $NP$ and Other Complete Sets
+Normal rank
@@ Property / cites work @@
+A note on structure and looking back applied to the relative complexity of computable functions
+Normal rank
@@ Property / cites work @@
+TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
+Normal rank
@@ Property / cites work @@
+Polynomial time computations in models of ET
@@ Property / cites work: Polynomial time computations in models of ET / rank @@
+Normal rank
@@ Property / cites work @@
+Completeness, Approximation and Density
@@ Property / cites work: Completeness, Approximation and Density / rank @@
+Normal rank
@@ Property / cites work @@
+Indexings of subrecursive classes
@@ Property / cites work: Indexings of subrecursive classes / 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 @@
+Simple Gödel Numberings, Isomorphisms, and Programming Properties
+Normal rank
@@ Property / cites work @@
+Q4153600
@@ Property / cites work: Q4153600 / rank @@
+Normal rank
@@ Property / cites work @@
+Reductions among polynomial isomorphism types
@@ Property / cites work: Reductions among polynomial isomorphism types / rank @@
+Normal rank
@@ Property / cites work @@
+Q3232283
@@ Property / cites work: Q3232283 / rank @@
+Normal rank
@@ Property / cites work @@
+Optimal Approximations and Polynomially Levelable Sets
+Normal rank
@@ Property / cites work @@
+Q5573961
@@ Property / cites work: Q5573961 / rank @@
+Normal rank
@@ Property / cites work @@
+Optimal enumerations and optimal gödel numberings
+Normal rank
@@ Property / cites work @@
+A uniform approach to obtain diagonal sets in complexity classes
+Normal rank