In this paper, we present a polynomial-time algorithm for the maximum clique problem, which implies P = NP. Our algorithm is based on a continuous game-theoretic representation of this problem and at its heart lies a discrete-time dynamical system. The rule of our dynamical system depends on a parameter such that if this parameter is equal to the maximum-clique size, the iterates of our dynamical system are guaranteed to converge to a maximum clique.


翻译:在本文中,我们为最大分类问题提出了一个多元时间算法,这意味着 P = NP。我们的算法基于对该问题的持续游戏理论表达,其核心是一个离散的时间动态系统。我们动态系统的规则取决于一个参数,如果这个参数等于最大分类大小,那么我们动态系统的迭代就能够保证与最大分类趋同。

0
下载
关闭预览

相关内容

【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
105+阅读 · 2019年10月9日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
18+阅读 · 2018年12月24日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
lightgbm algorithm case of kaggle(上)
R语言中文社区
8+阅读 · 2018年3月20日
Arxiv
0+阅读 · 2021年11月5日
Arxiv
0+阅读 · 2021年11月3日
VIP会员
相关资讯
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
18+阅读 · 2018年12月24日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
lightgbm algorithm case of kaggle(上)
R语言中文社区
8+阅读 · 2018年3月20日
Top
微信扫码咨询专知VIP会员