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

      0 references
      0 references
      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
      [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

      Identifiers

      0 references
      0 references
      0 references
      0 references