Satisfiability is quasilinear complete in NQL

  • 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

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Author:Claus Peter SchnorrGND
Parent Title (German):Journal of the Association for Computing Machinery
Publisher:Association for Computing Machinery
Place of publication:New York, NY
Document Type:Article
Date of Publication (online):2005/11/10
Year of first Publication:1978
Publishing Institution:Universit├Ątsbibliothek Johann Christian Senckenberg
Release Date:2005/11/10
Tag:NP-complete problems; clique problem; colorabdity; graph isomorphism; logical networks; nondetermmistlc Turing machines; satlsfiablhty
Page Number:10
First Page:136
Last Page:145
Source:Journal of the ACM (JACM), Volume 25 Issue 1 ,
Institutes:Informatik und Mathematik / Mathematik
Informatik und Mathematik / Informatik
Dewey Decimal Classification:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
Licence (German):License LogoDeutsches Urheberrecht