scientific article; zbMATH DE number 4101157

MaRDI QIDQ3826533zbMATH OpenFDO

Authors S. Shelah, Yuri Gurevich

Publication date 1989

zbMATH Keywords

complete problemsmachine-independent description of NLTnearly linear time computable functions NLTnondeterministic versionQL reductionsmall complexity classes

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• ON THE NOTION OF LINEAR TIME COMPUTABILITY
• Linear Time Algorithms and NP-Complete Problems
• scientific article; zbMATH DE number 515738
• Machine-Independent Characterizations and Complete Problems for Deterministic Linear Time
• Invariance properties of RAMs and linear time

Cited in

(30)

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