Name
Abstract | ||
|---|---|---|
We introduce the polynomial time version, in short less than or equal to(T)(P)-introreducibility, of the notion of introreducibility studied in Recursion Theory. We give a simpler proof of the known fact that a set is less than or equal to(T)(P)-introreducible if and only if it is in P. Our proof generalizes to virtually all the computation bounded reducibilities less than or equal to(r), showing that a set is less than or equal to(r)-introreducible if and only if it belongs to the minimum less than or equal to(r)-degree. It also holds for most unbounded reducibilities like less than or equal to(m), less than or equal to(c), less than or equal to(d), less than or equal to(p), less than or equal to(tt), etc., but it does not hold for less than or equal to(T). A very strong way for a set L to fail being less than or equal to(r)-introreducible is that L is not less than or equal to(r)-reducible to any coinfinite subset of L. We call such sets less than or equal to(r)-introimmune. It is known that less than or equal to(T)-introimmune sets exist but they are not arithmetical. In this paper we ask for which reducibilities less than or equal to(r) there exist arithmetical less than or equal to(r)-introimmune sets. We show that they exist for the reducibilities less than or equal to(c) and less than or equal to(m)(N). Finally, we prove separation results between introimmunities. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1007/s00224-002-1040-z | THEORY OF COMPUTING SYSTEMS |
Keywords | Field | DocType |
recursion theory,polynomial time | Discrete mathematics,Combinatorics,Arithmetic function,Reduction (recursion theory),Non-deterministic Turing machine,Comparability,Time complexity,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
36.0 | 1 | 1432-4350 |
Citations | PageRank | References |
3 | 0.53 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Patrizio Cintioli | 1 | 7 | 2.68 |
| Riccardo Silvestri | 2 | 1324 | 90.84 |