scientific article
From MaRDI portal
Publication:3975929
zbMath0744.03045MaRDI QIDQ3975929
Robert I. Soare, Homer, Steven, Ambos-Spies, Klaus
Publication date: 26 June 1992
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
minimal pairNP-completeoraclepolynomial-time reducibilitypolynomial-time degreePTIMEtoppolynomial many-one reductionsp-splittingelementary recursive EXPTIME-hard set
Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30)
Related Items