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 iterates of our dynamical system are guaranteed to converge to a fixed point that is not necessarily an equilibrium but we show that a maximum clique can be computed enter a neighborhood of a fixed point.


翻译:在本文中,我们给出了一个关于最大分类问题的多边-时间算法,这意味着 P = NP。我们的算法基于对该问题的持续的游戏理论表达,其核心是一个离散的时空动态系统。我们动态系统的迭代被保证会汇合到一个固定点,而这个点不一定是一个平衡,但我们表明,可以计算出一个最大分类,进入一个固定点的附近。

0
下载
关闭预览

相关内容

专知会员服务
41+阅读 · 2021年4月2日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
【DeepMind】强化学习教程,83页ppt
专知会员服务
151+阅读 · 2020年8月7日
【硬核书】群论,Group Theory,135页pdf
专知会员服务
124+阅读 · 2020年6月25日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
Hierarchically Structured Meta-learning
CreateAMind
25+阅读 · 2019年5月22日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Reinforcement Learning: An Introduction 2018第二版 500页
CreateAMind
11+阅读 · 2018年4月27日
随波逐流:Similarity-Adaptive and Discrete Optimization
我爱读PAMI
5+阅读 · 2018年2月6日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年7月16日
Arxiv
0+阅读 · 2021年7月15日
Arxiv
0+阅读 · 2021年7月14日
Implicit Maximum Likelihood Estimation
Arxiv
7+阅读 · 2018年9月24日
VIP会员
相关VIP内容
专知会员服务
41+阅读 · 2021年4月2日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
【DeepMind】强化学习教程,83页ppt
专知会员服务
151+阅读 · 2020年8月7日
【硬核书】群论,Group Theory,135页pdf
专知会员服务
124+阅读 · 2020年6月25日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
25+阅读 · 2019年5月22日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Reinforcement Learning: An Introduction 2018第二版 500页
CreateAMind
11+阅读 · 2018年4月27日
随波逐流:Similarity-Adaptive and Discrete Optimization
我爱读PAMI
5+阅读 · 2018年2月6日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员