Hardness of Finding Independent Sets in 2-Colorable Hypergraphs and of Satisfiable CSPs.
Rishi SaketPublished in: Computational Complexity Conference (2014)
Keyphrases
- phase transition
- constraint satisfaction
- np complete
- constraint satisfaction problems
- sat problem
- satisfiability problem
- random instances
- constraint propagation
- np hard
- hypertree decomposition
- learning theory
- constraint programming
- graph coloring
- randomly generated
- computational complexity
- cellular automata
- worst case
- upper bound
- search space
- lower bound