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。我们的算法基于对该问题的持续游戏理论表达,其核心是一个离散的时间动态系统。我们动态系统的规则取决于一个参数,如果这个参数等于最大分类大小,那么我们动态系统的迭代就能够保证与最大分类趋同。
相关内容
专知会员服务
13+阅读 · 2020年5月19日
专知会员服务
34+阅读 · 2019年10月17日
Arxiv
0+阅读 · 2021年11月1日
Arxiv
0+阅读 · 2021年10月29日
Arxiv
0+阅读 · 2021年10月29日
Arxiv
0+阅读 · 2021年10月28日
Arxiv
0+阅读 · 2021年10月28日
Arxiv
0+阅读 · 2021年10月27日
相关主题
相关VIP内容
专知会员服务
13+阅读 · 2020年5月19日
专知会员服务
34+阅读 · 2019年10月17日
相关资讯
相关论文
Arxiv
0+阅读 · 2021年11月1日
Arxiv
0+阅读 · 2021年10月29日
Arxiv
0+阅读 · 2021年10月29日
Arxiv
0+阅读 · 2021年10月28日
Arxiv
0+阅读 · 2021年10月28日
Arxiv
0+阅读 · 2021年10月27日
微信扫码咨询专知VIP会员