On Nondeterminism, Enumeration Reducibility and Polynomial Bounds

DOI10.1002/MALQ.19970430302zbMath0882.03042OpenAlexW1984891917MaRDI QIDQ4351919

Kate Copestake

Publication date: 1 October 1997

Published in: Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/malq.19970430302

zbMATH Keywords

minimal pairsrecursive setsnondeterminismrelative computabilityenumeration degreesenumeration reducibilitycomputable setsjump operatorpolynomial time reducibilitypolynomial time degreeconjunctive reducibilitypolynomial enumeration

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other degrees and reducibilities in computability and recursion theory (03D30) Turing machines and related notions (03D10)

Related Items (1)

Nondiamond theorems for polynomial time reducibility

Cites Work

• Unnamed Item
• On the Structure of Polynomial Time Reducibility

This page was built for publication: On Nondeterminism, Enumeration Reducibility and Polynomial Bounds