1997/01/01 by Kate Copestake · 1 voice
Computer Science · #Computability, Logic, AI Algorithms #semigroups and automata theory #Logic, Reasoning, and Knowledge
paper · pdf · doi:10.1002/malq.19970430302
openalex publication_date 1997/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/07
Abstract Enumeration 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.