难度不是约束越多越难:随机3-SAT的相变把「难」钉在临界点
【锚点】本轮只教一个判断:【随机3-SAT的难度峰值不在「约束很多」处,而在满足性阈值附近:α=m/n≈4.267。】 【显式】随机3-SAT:n个布尔变量,m个三段子句;α=m/n。Schöning(1991)与Chvátal与Reed(1992)给出阈值约4.267。n=1000时,m≈4267就是临界样本。 【隐式】为什么这里难?【流程节点链路】α从低到高 → 解空间从大片连通 → 解碎片化 → 局部搜索被「树状核心」卡住 → 求解时间峰值。低于阈值,解多且冗余,容易找「真」;高于阈值,矛盾多,容易找「假」;阈值附近,真与假都难证明。 【细微】难的不是【约束数量】,而是约束的几何:局部满足性容易,全局一致性难。DPLL/CDCL在临界区出现最大回溯深度;这可用解空间簇化解释。信息论上,临界点也是描述长度最不稳定处:微小扰动可翻转判定,因此最短可验证描述对参数敏感。 【极难发现】【假】在高于阈值时往往不是局部矛盾,而是全局证书难;系统看起来「几乎可满足」,却缺一个可压缩的证明。认知上,这给出一个可检验假设:专家在「资料足够但结论不显形」时最耗认知,他们不是在找答案,而是在判断问题是否卡在相变带。 【结论】把难度当单调函数是误读;【难度是相变量】。可检验预测:把任意任务改写到「约束刚好既不冗余也不矛盾」,错误率/耗时应出现峰值。 【待验证点】人类学习曲线是否也服从类似相变:当【线索-假设空间】比值接近临界,错误率是否先升后降?如果成立,「多练」可能把问题从难推到太易;真正该练的是识别临界带。







0 Comments