In this paper, we examine Quigley's "A Polynomial Time Algorithm for 3SAT" [Qui24]. Quigley claims to construct an algorithm that runs in polynomial time and determines whether a boolean formula in 3CNF form is satisfiable. Such a result would prove that 3SAT $\in \text{P}$ and thus $\text{P} = \text{NP}$. We show Quigley's argument is flawed by providing counterexamples to several lemmas he attempts to use to justify the correctness of his algorithm. We also provide an infinite class of 3CNF formulas that are unsatisfiable but are classified as satisfiable by Quigley's algorithm. In doing so, we prove that Quigley's algorithm fails on certain inputs, and thus his claim that $\text{P} = \text{NP}$ is not established by his paper.


翻译:暂无翻译

0
下载
关闭预览

相关内容

论文(Paper)是专知网站核心资料文档,包括全球顶级期刊、顶级会议论文,及全球顶尖高校博士硕士学位论文。重点关注中国计算机学会推荐的国际学术会议和期刊,CCF-A、B、C三类。通过人机协作方式,汇编、挖掘后呈现于专知网站。
FlowQA: Grasping Flow in History for Conversational Machine Comprehension
专知会员服务
34+阅读 · 2019年10月18日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
31+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
163+阅读 · 2019年10月12日
Hierarchically Structured Meta-learning
CreateAMind
27+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
29+阅读 · 2019年5月18日
STRCF for Visual Object Tracking
统计学习与视觉计算组
15+阅读 · 2018年5月29日
IJCAI | Cascade Dynamics Modeling with Attention-based RNN
KingsGarden
13+阅读 · 2017年7月16日
From Softmax to Sparsemax-ICML16(1)
KingsGarden
74+阅读 · 2016年11月26日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
3+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
Arxiv
12+阅读 · 2023年5月31日
Arxiv
21+阅读 · 2019年3月25日
VIP会员
相关VIP内容
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
27+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
29+阅读 · 2019年5月18日
STRCF for Visual Object Tracking
统计学习与视觉计算组
15+阅读 · 2018年5月29日
IJCAI | Cascade Dynamics Modeling with Attention-based RNN
KingsGarden
13+阅读 · 2017年7月16日
From Softmax to Sparsemax-ICML16(1)
KingsGarden
74+阅读 · 2016年11月26日
相关基金
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
3+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
Top
微信扫码咨询专知VIP会员