Refine
Year of publication
- 1978 (1)
Document Type
- Article (1)
Language
- English (1) (remove)
Has Fulltext
- yes (1)
Is part of the Bibliography
- no (1) (remove)
Keywords
- logical networks (1) (remove)
Institute
- Mathematik (1) (remove)
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