Satisfiability Is Quasilinear Complete in NQL

DOI10.1145/322047.322060zbMath0364.68056OpenAlexW2085938002WikidataQ129444458 ScholiaQ129444458MaRDI QIDQ4139688

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

Related Items (22)

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

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