TY  - JOUR
A1  - Schnorr, Claus Peter
T1  - Satisfiability is quasilinear complete in NQL
T2  - Journal of the Association for Computing Machinery
N2  - Considered are the classes QL (quasilinear) and NQL (nondet quasllmear) of all those problems that can be solved by deterministic (nondetermlnlsttc, respectively) Turmg machines in time O(n(log n) ~) for some k Effloent algorithms have time bounds of th~s type, it is argued. Many of the "exhausUve search" type problems such as satlsflablhty and colorabdlty are complete in NQL with respect to reductions that take O(n(log n) k) steps This lmphes that QL = NQL iff satisfiabdlty is m QL CR CATEGORIES: 5.25
KW  - NP-complete problems
KW  - nondetermmistlc Turing machines
KW  - logical networks
KW  - satlsfiablhty
KW  - colorabdity
KW  - graph isomorphism
KW  - clique problem
Y1  - 2005
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/3327
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30-20860
VL  - 25
IS  - 1
SP  - 136
EP  - 145
PB  - Association for Computing Machinery
CY  - New York, NY
ER  -