scientific article; zbMATH DE number 3984572

From MaRDI portal
Publication:3747724





[For the entire collection see Zbl 0587.00019.] The following question is addressed: If for a set A, \(DEXT(A)=DEXT\), does it mean \(A\in {\mathcal P} ?\) Here DEXT refers to deterministic exponential time. A set satisfying \(DEXT(A)=DEXT\) is called exponentially low (DEXT- low). This is generalisation of a notion of lowness introducted by Schöning, where \(A\in {\mathcal N}{\mathcal P}\) is low if \(\Sigma^ P_ i(A)=\Sigma^ P_ i\) for some i. In some sense such sets do not contain much information. It was already known that every set in \({\mathcal P}\) is DEXT-low. The main result of section 3 is to show that for sets with small generalised Kolmogorov complexity DEXT-low sets are in \({\mathcal P}\). (Generalised Kolmogorov complexity measures informally how far and how fast a string can be compressed.) This last result shows that to find DEXT-low sets not in \({\mathcal P}\), we need to consider sets which do not have small Kolmogorov complexity - so must be structurally complex. A set which is not of small Kolmogorov complexity is chosen and then a sparse subset E of this set. It is shown how a deterministic exponential Turing machine computation with oracle E can be simulated by a deterministic Turing machine with no oracle. Thus, this E is an example of a DEXT-low set not in \({\mathcal P}.\) The last section considers lowness in the polynomial and exponential hierarchies. First of all it is shown that if a set is \(\Sigma^ P_ i\)-low then it is \(\Sigma^ E_ i\)-low. The last major result is to show that for sparse sets S, if S is \(\Sigma^ E_ i\)-low then S is also \(\Sigma^ P_ i\)-low. This makes use of a technical lemma which states that if A is of a certain compact description and \(\Sigma^ E_ i\)-low then it is \(\Sigma^ P_ i\)-low.











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 Q3747724)