scientific article; zbMATH DE number 4101157

From MaRDI portal
Publication:3826533





[For the entire collection see Zbl 0669.00003.] Small complexity classes, say, linear-time, seem to be very interesting to be investigated, in particular from a practical viewpoint. Unfortunately the class of linear-time computable functions is badly defined, because it is sensitive to the considered machine model of computation. Authors introduce a class of nearly linear time computable functions NLT\(=\cup_{c\in \omega}DTIME[n(\log n)^ c]\), which appears to be independent of a particular model chosen among RAM, Kolmogorov machines, Schönhage machines, random access Turing machines, etc., but not standard multitape Turing machines (which are believed to be not appropriate to this definition). This class seems to be the minimal robust class w.r.t. time complexity. A machine-independent description of NLT is also given. \textit{C. P. Schnorr} [J. Assoc. Comput. Mach. 25, 136-145 (1978; Zbl 0364.68056)] chose multitape Turing machines with linear types, defined the class \(QL=\cup_{c\in \omega}DTIME[n(\log n)^ c]\) and showed that SAT (satisfiability problem for Boolean formulae) is complete for the nondeterministic version of QL, NQL, w.r.t. QL reduction. It remains unknown whether NLT properly contains QL, but the nondeterministic version of NLT, NNLT, coincides with NQL. Finally, the authors find some natural problem which is NLT-complete w.r.t. QL reduction.




Cited in
(30)








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