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
下载
关闭预览

相关内容

Linux导论,Introduction to Linux,96页ppt
专知会员服务
82+阅读 · 2020年7月26日
强化学习最新教程,17页pdf
专知会员服务
182+阅读 · 2019年10月11日
ResNet, AlexNet, VGG, Inception:各种卷积网络架构的理解
全球人工智能
20+阅读 · 2017年12月17日
【推荐】用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月13日
VIP会员
相关主题
相关VIP内容
Linux导论,Introduction to Linux,96页ppt
专知会员服务
82+阅读 · 2020年7月26日
强化学习最新教程,17页pdf
专知会员服务
182+阅读 · 2019年10月11日
相关资讯
ResNet, AlexNet, VGG, Inception:各种卷积网络架构的理解
全球人工智能
20+阅读 · 2017年12月17日
【推荐】用Tensorflow理解LSTM
机器学习研究会
36+阅读 · 2017年9月11日
【推荐】GAN架构入门综述(资源汇总)
机器学习研究会
10+阅读 · 2017年9月3日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
相关论文
Top
微信扫码咨询专知VIP会员