article · 1994
The Structural Complexity Column
By Juris Hartmanis, Juris Hartmanis, Richard Chang
Cited by 0Abstract and details only
Abstract
This column addresses the following questions about the complexity of approximating the CLIQUE problem. 1. Is finding the vertices of the largest clique more difficult than merely finding the vertices of a 2-approximate clique (that is, a clique with at least half the size of the largest clique)? 2. What computational resources can be used to find the vertices of a 2-approximate clique? 3. Could fewer resources be used? The results of recent studies (by Chang, Gasarch and Lund; Khanna, Motwani, Sudan and Vazirani; and Crescenzi, Kann and Trevisan) on the complexity of NPapproximation problems yield the following answers: (1) Yes, unless the Polynomial Hierarchy collapses; (2) Nondeterministic polynomial time with log log n+O(1) queries to SAT; and (3) Not unless the Polynomial Hierarchy collapses. Surprisingly, the proof of these results depends on the fact that a collapse of the Boolean Hierarchy implies a collapse of the Polynomial Hierarchy. y Supported in part by Na...
Cite this paper
Hartmanis, B. J., Hartmanis, J., & Chang, R. (1994). The Structural Complexity Column.
Hartmanis, By Juris, et al. “The Structural Complexity Column.” 1994.
Hartmanis, By Juris, Juris Hartmanis, and Richard Chang. 1994. “The Structural Complexity Column.”
Hartmanis, B.J., Hartmanis, J. and Chang, R. (1994) ‘The Structural Complexity Column’.
@article{hartmanis1994structural,
title = {{The Structural Complexity Column}},
author = {Hartmanis, By Juris and Hartmanis, Juris and Chang, Richard},
year = {1994}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.