Approximating Clique is Almost NP-Complete (Preliminary Version)
Uriel FeigeShafi GoldwasserLászló LovászShmuel SafraMario SzegedyPublished in: FOCS (1991)
Keyphrases
- preliminary version
- np complete
- np hard
- constraint satisfaction problems
- computational complexity
- randomly generated
- maximum weight
- polynomial time complexity
- satisfiability problem
- conjunctive queries
- np complete problems
- pspace complete
- phase transition
- sat problem
- polynomially solvable
- conp complete
- neural network
- upper bound
- data complexity
- bounded treewidth
- scheduling problem
- knowledge base