How hard are n 2 -hard problems?
- 1 June 1994
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGACT News
- Vol. 25 (2) , 83-85
- https://doi.org/10.1145/181462.181465
Abstract
Many of the " n 2 -hard" problems described by Gajentaan and Overmars can be solved using limited nondeterminism or other sharply-bounded quantifiers. Thus we suggest that problems are not among the hardest problems solvable in quadratic timeKeywords
This publication has 3 references indexed in Scilit:
- Computational geometryACM SIGACT News, 1994
- Nondeterminism within $P^ * $SIAM Journal on Computing, 1993
- Satisfiability Is Quasilinear Complete in NQLJournal of the ACM, 1978