Enumeration reducibility, nondeterministic computations and relative computability of partial functions

1990/01/01 by S. Barry Cooper · 1 voice · 2 citations
Computer Science · Mathematics · #Benford’s Law and Fraud Detection #Computability, Logic, AI Algorithms #semigroups and automata theory

paper · doi:10.1007/bfb0086114

crossref issued 1990/01/01 · crossref published 1990/01/01 · crossref published-print 1990/01/01 · openalex publication_date 1990/01/01 · crossref published-online 2006/10/02 · crossref created 2006/11/24 · crossref deposited 2019/04/22 · openalex created_date 2025/10/10 · openalex updated_date 2025/11/06 · crossref indexed 2026/03/02

Cited by

• On Nondeterminism, Enumeration Reducibility and Polynomial Bounds
• Strong Enumeration Reducibilities

Discussions

• Update: proofs of this theorem are annoyingly hard to find. Selman's original 1971 proof is hard to read. There's a 1978 proof by Rozinas, but it's in Russian. Cooper's proof quoted above appears inco [bsky, 0 points, 1 comments]