Linear Time Algorithms and NP-Complete Problems

DOI10.1137/S0097539791223206MaRDI QIDQ4302285zbMATH OpenOpenAlexFDO

Authors Etienne Grandjean

Publication date 14 August 1994

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539791223206

zbMATH Keywords

complexity theory polynomial

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 515738
• scientific article; zbMATH DE number 4101157
• scientific article; zbMATH DE number 515731
• On NP-completeness for linear machines
• Sorting, linear time and the satisfiability problem

Cited in

(16)

• Sorting, linear time and the satisfiability problem
• Exact complexity of problems of incompletely specified automata
• Nonerasing, counting, and majority over the linear time hierarchy
• Linear time and the power of one first-order universal quantifier
• ON THE NOTION OF LINEAR TIME COMPUTABILITY
• Nondeterministic linear-time tasks may require substantially nonlinear deterministic time in the case of sublinear work space
• A NORMAL FORM FOR FIRST-ORDER LOGIC OVER DOUBLY-LINKED DATA STRUCTURES
• scientific article; zbMATH DE number 4101157 (Why is no real title available?)
• scientific article; zbMATH DE number 515731 (Why is no real title available?)
• scientific article; zbMATH DE number 515738 (Why is no real title available?)
• scientific article; zbMATH DE number 1778409 (Why is no real title available?)
• Machine-Independent Characterizations and Complete Problems for Deterministic Linear Time
• Algebraic and logical characterizations of deterministic linear time classes
• Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle
• Graph properties checkable in linear time in the number of vertices
• On the expressive power of monadic least fixed point logic

This page was built for publication: Linear Time Algorithms and NP-Complete Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4302285)