scientific article; zbMATH DE number 3877163

From MaRDI portal
Publication:3344189





[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.











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)