×

zbMATH — the first resource for mathematics

Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract). (English) Zbl 1345.68152
Proceedings of the 26th annual ACM symposium on theory of computing, STOC ’94, Montreal, Canada, May 23–25, 1994. New York, NY: Association for Computing Machinery (ACM) (ISBN 0-89791-663-8). 449-458 (1994).

MSC:
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q25 Analysis of algorithms and problem complexity
05C85 Graph algorithms (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI