Refine
Year of publication
Document Type
- Article (11)
- Preprint (10)
- Report (8)
- Conference Proceeding (2)
- Part of a Book (1)
Language
- English (32)
Has Fulltext
- yes (32)
Is part of the Bibliography
- no (32)
Keywords
- LLL-reduction (3)
- computational complexity (2)
- segments (2)
- Block Korkin—Zolotarev reduction (1)
- Dirichlet bound (1)
- Householder reflection (1)
- Knapsack problem (1)
- Kongress (1)
- Korkin—Zolotarev reduction (1)
- Kryptosystem (1)
Institute
- Mathematik (31)
- Informatik (30)
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