In this paper we have to demonstrate that if we claim to have an algorithm that solves CSAT in polynomial time with a DTM (Deterministic Turing Machine), then we have to admit that: there is a counterexample that invalidates the correctness of the algorithm. This is because if we suppose that it can prove that an elenkhos formula (a formula that lists the negated codes of all models) is a contradiction, and if we change exactly a specific boolean variable of that formula, then we have proven that: in this case the algorithm will always fail.


翻译:在这份文件中,我们必须证明,如果我们声称有一个算法,用DTM(确定性图灵机)在多元时间用DTM(确定性图灵机)解决了CSAT,那么我们就必须承认:有一个反比的例子使算法的正确性失效。 这是因为如果我们假设它能够证明埃伦霍斯公式(列出所有模型的否定代码的公式)是矛盾的,如果我们完全改变了该公式的具体布林变量,那么我们就证明了:在这种情况下,算法将永远失败。

0
下载
关闭预览

相关内容

专知会员服务
16+阅读 · 2021年8月24日
专知会员服务
123+阅读 · 2020年9月8日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
(OpenCV/Keras)用手势控制的计算器
机器学习研究会
3+阅读 · 2018年3月4日
ResNet, AlexNet, VGG, Inception:各种卷积网络架构的理解
全球人工智能
19+阅读 · 2017年12月17日
【推荐】ResNet, AlexNet, VGG, Inception:各种卷积网络架构的理解
机器学习研究会
20+阅读 · 2017年12月17日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【推荐】决策树/随机森林深入解析
机器学习研究会
5+阅读 · 2017年9月21日
【推荐】用Tensorflow理解LSTM
机器学习研究会
36+阅读 · 2017年9月11日
【推荐】GAN架构入门综述(资源汇总)
机器学习研究会
10+阅读 · 2017年9月3日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2022年1月17日
Arxiv
0+阅读 · 2022年1月15日
Arxiv
0+阅读 · 2022年1月15日
Arxiv
0+阅读 · 2022年1月13日
Meta-Learning to Cluster
Arxiv
17+阅读 · 2019年10月30日
A Probe into Understanding GAN and VAE models
Arxiv
9+阅读 · 2018年12月13日
VIP会员
相关主题
相关VIP内容
专知会员服务
16+阅读 · 2021年8月24日
专知会员服务
123+阅读 · 2020年9月8日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
相关资讯
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
(OpenCV/Keras)用手势控制的计算器
机器学习研究会
3+阅读 · 2018年3月4日
ResNet, AlexNet, VGG, Inception:各种卷积网络架构的理解
全球人工智能
19+阅读 · 2017年12月17日
【推荐】ResNet, AlexNet, VGG, Inception:各种卷积网络架构的理解
机器学习研究会
20+阅读 · 2017年12月17日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【推荐】决策树/随机森林深入解析
机器学习研究会
5+阅读 · 2017年9月21日
【推荐】用Tensorflow理解LSTM
机器学习研究会
36+阅读 · 2017年9月11日
【推荐】GAN架构入门综述(资源汇总)
机器学习研究会
10+阅读 · 2017年9月3日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
相关论文
Arxiv
0+阅读 · 2022年1月17日
Arxiv
0+阅读 · 2022年1月15日
Arxiv
0+阅读 · 2022年1月15日
Arxiv
0+阅读 · 2022年1月13日
Meta-Learning to Cluster
Arxiv
17+阅读 · 2019年10月30日
A Probe into Understanding GAN and VAE models
Arxiv
9+阅读 · 2018年12月13日
Top
微信扫码咨询专知VIP会员