Where The Really Hard Problems Really Are?

on YouTube ↗01h 00m

" summary

Random k‑SAT shows sharp satisfiability transitions at a clause‑to‑variable ratio α and statistical‑physics methods (notably survey propagation and belief propagation) give explicit formulas for several thresholds: clustering, condensation, rigidity and the satisfiability limit. Concrete claims: survey propagation solves million‑variable random instances up to near the predicted satisfiability α, belief propagation estimates counts correctly only below condensation, and frozen clusters (extensive frozen variables) correlate with algorithmic failure. Locked CSPs force clustering=freezing and common solvers fail at that point; planted 5‑coloring is provably information‑easy around degree ≈13 but algorithmically hard until degree 16.

AI-written summary · about

" chapters (14)

1. 0:00Start
2. 2:35EXAMPLE: LEARNING WITH NEURAL NETWORKS...
3. 3:10AVERAGE-CASE COMPLEXITY
4. 6:06RANDOM SATISFIABILITY
5. 8:40PHYSICS IN THE GAME
6. 10:18GETTING MORE PRECISE
7. 11:16STRUCTURE OF SOLUTIONS
8. 34:39LOCKED CSP
9. 37:55SPACE OF SOLUTIONS
10. 39:34CONCLUSION ON LOCKED CSI
11. 42:44PLANTED PHASE TRANSITIONS
12. 46:45METASTABILITY
13. 48:36HARD PHASE CHALLENGE
14. 49:10SUMMARY