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
Author: | Claus Peter SchnorrGND |
---|---|
URN: | urn:nbn:de:hebis:30-20860 |
Parent Title (German): | Journal of the Association for Computing Machinery |
Publisher: | Association for Computing Machinery |
Place of publication: | New York, NY |
Document Type: | Article |
Language: | English |
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 |
Volume: | 25 |
Issue: | 1 |
Page Number: | 10 |
First Page: | 136 |
Last Page: | 145 |
Source: | Journal of the ACM (JACM), Volume 25 Issue 1 , http://portal.acm.org/ft_gateway.cfm?id=322060&type=pdf&coll=GUIDE&dl=GUIDE&CFID=57806729&CFTOKEN=16714017 |
HeBIS-PPN: | 186939507 |
Institutes: | Informatik und Mathematik / Mathematik |
Informatik und Mathematik / Informatik | |
Dewey Decimal Classification: | 5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik |
Licence (German): | Deutsches Urheberrecht |