Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses.
Chris JonesKunal MarwahaJuspreet Singh SandhuJonathan ShiPublished in: CoRR (2022)
Keyphrases
- constraint satisfaction problems
- random instances
- constraint satisfaction
- np complete
- phase transition
- arc consistency
- randomly generated
- lower bound
- symmetry breaking
- illumination conditions
- maintaining arc consistency
- constraint problems
- video conferencing
- np hard
- search space
- neural network
- data sets
- information theoretic
- worst case
- stereo camera
- non binary
- soft constraints
- computational complexity
- solving constraint satisfaction problems