scientific article; zbMATH DE number 3877163
[For the entire collection see Zbl 0538.00005.] We prove easy recursion-theoretic results which have as corollaries generalisations of existing diagonalisation theorems on complexity classes: Roughly speaking, almost no reasonable (time or space) complexity class can be expressed as the union of two recursively presentable classes which are both properly contained in it and closed under finite variations (e.g. unless \(NP=P,\) \(NP\neq P\cup \{NP-\)complete languages\(\})\); and, consequently, the non-trivial complement of one complexity class in another one (e.g. \((NP\setminus P),\) provided \(NP\neq P)\) is almost never recursively presentable.
- The recursion-theoretic structure of complexity classes
- Index sets and presentations of complexity classes
- scientific article; zbMATH DE number 3841832 (Why is no real title available?)
- scientific article; zbMATH DE number 3873308 (Why is no real title available?)
- scientific article; zbMATH DE number 3596249 (Why is no real title available?)
- scientific article; zbMATH DE number 512990 (Why is no real title available?)
- The non-recursive power of erroneous computation
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3344189)