Satisfiability Is Quasilinear Complete in NQL

DOI10.1145/322047.322060MaRDI QIDQ4139688zbMATH OpenOpenAlexWikidataFDO

Authors Claus Peter Schnorr

Publication date 1978

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL http://publikationen.ub.uni-frankfurt.de/files/3327/p136-schnorr.pdf

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Turing machines and related notions (03D10)

Cited in

(22)

• Algebraic and logical characterizations of deterministic linear time classes
• Local reduction
• Effective guessing has unlikely consequences
• Computation models and function algebras
• On parallel hierarchies and R ki
• Linear time transformations between combinatorial problems
• Invariance properties of RAMs and linear time
• Nonuniform ACC circuit lower bounds
• The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness
• Observations on complete sets between linear time and polynomial time
• Short propositional formulas represent nondeterministic computations
• Sorting, linear time and the satisfiability problem
• Amplifying circuit lower bounds against polynomial time, with applications
• Shorter arithmetization of nondeterministic computations
• On quasilinear-time complexity theory
• Nonerasing, counting, and majority over the linear time hierarchy
• Power indices and easier hard problems
• On parallel hierarchies and R_k^i
• Time-space tradeoffs for satisfiability
• Data independence of read, write, and control structures in PRAM computations
• Rational presented metric spaces and complexity, the case of the space of real functions uniformly continuous on a compact interval
• Local reductions

This page was built for publication: Satisfiability Is Quasilinear Complete in NQL

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