scientific article; zbMATH DE number 4101157
[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.
- Invariance properties of RAMs and linear time
- A descriptive complexity approach to the linear hierarchy.
- Time-space tradeoffs for satisfiability
- Lower bounds on the complexity of recognizing SAT by Turing machines
- Local reduction
- Sorting, linear time and the satisfiability problem
- Nonerasing, counting, and majority over the linear time hierarchy
- Computing absolutely normal numbers in nearly linear time
- Foremost non-stop journey arrival in linear time
- Linear-size constant-query IOPs for delegating computation
- Constrained synchronization and commutativity
- Time polynomial in input or output
- Nonuniform ACC circuit lower bounds
- ON THE NOTION OF LINEAR TIME COMPUTABILITY
- Local reductions
- Amplifying circuit lower bounds against polynomial time, with applications
- scientific article; zbMATH DE number 3954277 (Why is no real title available?)
- scientific article; zbMATH DE number 515738 (Why is no real title available?)
- Linear Time Algorithms and NP-Complete Problems
- Machine-Independent Characterizations and Complete Problems for Deterministic Linear Time
- Combinatorial PCPs with efficient verifiers
- Shorter arithmetization of nondeterministic computations
- Algebraic and logical characterizations of deterministic linear time classes
- Solving LP relaxations of some NP-hard problems is as hard as solving any linear program
- Graph properties checkable in linear time in the number of vertices
- Computation models and function algebras
- On quasilinear-time complexity theory
- The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness
- Quantitative coding and complexity theory of \textit{continuous} data. I: Motivation, definition, consequences
- On exponential-time hypotheses, derandomization, and circuit lower bounds
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)