
AbstractEnumeration reducibility is a notion of relative computability between sets of natural numbers where only positive information about the sets is used or produced. Extending e‐reducibility to partial functions characterises relative computability between partial functions. We define a polynomial time enumeration reducibility that retains the character of enumeration reducibility and show that it is equivalent to conjunctive non‐deterministic polynomial time reducibility. We define the polynomial time e‐degrees as the equivalence classes under this reducibility and investigate their structure on the recursive sets, showing in particular that the pe‐degrees of the computable sets are dense and do not form a lattice, but that minimal pairs exist. We define a jump operator and use it to produce a characterisation of the polynomial hierarchy.
nondeterminism, Complexity of computation (including implicit computational complexity), relative computability, minimal pairs, jump operator, enumeration reducibility, polynomial time degree, Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.), Models of computation (Turing machines, etc.), polynomial enumeration, conjunctive reducibility, Turing machines and related notions, polynomial time reducibility, recursive sets, Other degrees and reducibilities in computability and recursion theory, Complexity classes (hierarchies, relations among complexity classes, etc.), computable sets, enumeration degrees
nondeterminism, Complexity of computation (including implicit computational complexity), relative computability, minimal pairs, jump operator, enumeration reducibility, polynomial time degree, Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.), Models of computation (Turing machines, etc.), polynomial enumeration, conjunctive reducibility, Turing machines and related notions, polynomial time reducibility, recursive sets, Other degrees and reducibilities in computability and recursion theory, Complexity classes (hierarchies, relations among complexity classes, etc.), computable sets, enumeration degrees
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
