关键词computational complexity theory
搜索结果 - 6
- ICML本地与全局可解释性：一个计算复杂性角度
使用计算复杂性理论评估机器学习模型的局部和全局解释性，证明了局部和全局解释之间的对偶性以及某些全局解释形式的独特性，并比较了线性模型、决策树和神经网络在计算解释复杂度方面的差异。
- SAT 需要耗尽搜索
本文通过构造极难的 CSP（具有大域）和 SAT（具有长子句）例子，证明这些例子无法在不进行详尽搜索的情况下求解，从而得出 P≠NP 的结论，这种建设性方法对证明不可能性结果非常不同，并且缺少计算复杂性理论中当前使用的方法。
- 用深度神经网络高效表征量子多体状态
深度神经网络具有很高的表示能力，能够高效地表示大多数物理态，然而浅层神经网络在计算复杂度理论中的一些较高层次上不能够高效地表示这些态。
- 稀疏主成分估计中的统计和计算折衷
通过研究计算复杂性理论，发现在满足一定限制的协方差集中条件下存在有效的样本大小范围，在此范围内无法有随机多项式时间算法达到最佳极小风险率；对著名的半定松弛估计方法的理论性能进行研究，揭示了统计效率和计算效率之间微妙的相互作用，此方法为多维数 - 只有在聚类无关紧要时才很困难
本文提出了一个基于度量空间的 “好聚类” 的理论框架，展示了如果存在好的聚类，则在许多情况下可以轻易地找到它，因此与流行观点相反，聚类不应被视为一项艰苦的任务。
- 哲学家为何应关注计算复杂性
论文阐述了计算复杂性理论对于数学知识、强人工智能辩论、计算主义、逻辑无知问题、彭加莫的格鲁谜题、量子力学基础、经济理性、闭合类时曲线等哲学问题的影响，并讨论了计算复杂性理论本身受益于哲学分析的方面。