scientific article
From MaRDI portal
zbMath0673.03026MaRDI QIDQ3826533
Publication date: 1989
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
complete problemsmachine-independent description of NLTnearly linear time computable functions NLTnondeterministic versionQL reductionsmall complexity classes
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)
Related Items
Invariance properties of RAMs and linear time, Algebraic and logical characterizations of deterministic linear time classes, Local Reductions, Local reduction, Nonuniform ACC Circuit Lower Bounds, Amplifying circuit lower bounds against polynomial time, with applications, Real-time computability of real numbers by chemical reaction networks, Graph properties checkable in linear time in the number of vertices, Linear-size constant-query IOPs for delegating computation, Computation models and function algebras, A descriptive complexity approach to the linear hierarchy., Combinatorial PCPs with efficient verifiers, Shorter arithmetization of nondeterministic computations, Constrained synchronization and commutativity, On quasilinear-time complexity theory, The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness, Time polynomial in input or output, Computing absolutely normal numbers in nearly linear time, Sorting, linear time and the satisfiability problem, Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program, Time-space tradeoffs for satisfiability, Nonerasing, counting, and majority over the linear time hierarchy, Lower bounds on the complexity of recognizing SAT by Turing machines
