Algebraic and logical characterizations of deterministic linear time classes

DOI10.1007/BFb0023481zbMath1498.68119MaRDI QIDQ5048946

Thomas Schwentick

Publication date: 9 November 2022

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Graph properties checkable in linear time in the number of vertices

Cites Work

• A new recursion-theoretic characterization of the polytime functions
• Invariance properties of RAMs and linear time
• Sorting, linear time and the satisfiability problem
• An algebra and a logic for \(NC^ 1\)
• ON THE NOTION OF LINEAR TIME COMPUTABILITY
• A Nontrivial Lower Bound for an NP Problem on Automata
• A Natural NP-Complete Problem with a Nontrivial Lower Bound
• Satisfiability Is Quasilinear Complete in NQL
• Linear Time Algorithms and NP-Complete Problems
• Tailoring recursion for complexity
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Algebraic and logical characterizations of deterministic linear time classes