No label defined (Q3826533)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4101157
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 4101157 |
Statements
1989
0 references
complete problems
0 references
small complexity classes
0 references
nearly linear time computable functions NLT
0 references
machine-independent description of NLT
0 references
QL reduction
0 references
nondeterministic version
0 references
0.8838520646095276
0 references
0.800122082233429
0 references
0.7487192749977112
0 references
0.7487192153930664
0 references
[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.
0 references