Basicdefinitionsandterminology A propositionallogic formula ,alsocalled Booleanexpression ,isbuiltfrom variables ,operatorsAND( conjunction ,alsodenotedby∧),OR( disjunction ,∨),NOT( negation ,),andparentheses.Aformulaissaidtobe satisfiable ifitcanbemadeTRUEbyassigningappropriate logicalvalues (i.e.TRUE,FALSE)toitsvariables.The Booleansatisfiabilityproblem ( SAT )is,givenaformula,tocheckwhetheritissatisfiable.This decisionproblem isofcentralimportanceinvariousareasof computerscience ,including theoreticalcomputerscience , complexitytheory , algorithmics , cryptography and artificialintelligence . 命题逻辑公式（也称为布尔表达式），由变量、与运算符 ∧ 、或运算符 ∨ 、非运算符 和括号组成。设定适当的逻辑变量值使逻辑表达式的值为真，就说逻辑表达式是能够满足的。布尔可满足性问题（SAT）就是检查逻辑表达式是否是可满足的。这个判定问题是计算机科学，包括计算机理论、复杂性理论、算法、密码学和人工智能众多领域的核心重要问题。 ThereareseveralspecialcasesoftheBooleansatisfiabilityprobleminwhichtheformulasarerequiredtohaveaparticularstructure.A literal iseitheravariable,thencalled positiveliteral ,orthenegationofavariable,thencalled negativeliteral .A clause isadisjunctionofliterals(orasingleliteral).Aclauseiscalled Horn clause ifitcontainsatmostonepositiveliteral.Aformulaisin conjunctivenormalform ( CNF )ifitisaconjunctionofclauses(orasingleclause).Forexample, x 1 isapositiveliteral, x 2 isanegativeliteral, x 1 ∨ x 2 isaclause,and( x 1 ∨ x 2 )∧( x 1 ∨ x 2 ∨ x 3 )∧ x 1 isaformulainconjunctivenormalform,its1stand3rdclauseareHornclauses,butits2ndclauseisnot.Theformulaissatisfiable,choosing x 1 =FALSE, x 2 =FALSE,and x 3 arbitrarily,since(FALSE∨FALSE)∧(FALSE∨FALSE∨ x 3 )∧FALSEevaluatesto(FALSE∨TRUE)∧(TRUE∨FALSE∨ x 3 )∧TRUE,andinturntoTRUE∧TRUE∧TRUE(i.e.toTRUE).Incontrast,theCNFformula a ∧ a ,consistingoftwoclausesofoneliteral,isunsatisfiable,sincefor a =TRUEand a =FALSEitevaluatestoTRUE∧TRUE(i.e.toFALSE)andFALSE∧FALSE(i.e.againtoFALSE),respectively. 一些具体情况下，布尔满足性问题表达式要求有特定的结构。逻辑变量叫正文字，它的非运算形式叫反文字，子句是它们的或运算形式（包括一个文字）。最多有一个正文字的子句叫强子句。子句进行与运算的表达式叫合取范式（CNF）。例如， x 1 是正文字， x 2 是反文字， x 1 ∨ x 2 就是一个子句。而( x 1 ∨ x 2 )∧( x 1 ∨ x 2 ∨ x 3 )∧ x 1 是合取范式。此式的第一和第三子句是强子句，第二个子句不是。选择 x 1 =假, x 2 =假, x 3 任意，从(假∨假)∧(假∨假∨ x 3 )∧假，得出(假∨真)∧(真∨假∨ x 3 )∧真,子句值运算为真∧真∧真(即结果为真)。 批注：真够啰嗦的！
我为相关计算数学打开一扇门 姜咏江 事物之间有关还是无关，这种关系称为相关。引起事物相关最基本的东西称为因素。因素是构成事物的基本要素。例如，人是事物。构成人最基本的是基因，基因组合构成细胞，细胞组合构成器官，器官组合才构成人。用集合论的观点来看，事物就是带有包含层次的集合。基因构成子集，子集构成细胞、器官和人。 因素也是事物，事物都有两种对立的状态，用数码表示就是 0 和 1 。 1 和 0 的意义很多，例如“生，死”“有，无”“是，非”， ... 。如此一来，因素就可以用逻辑变量 x 来表示。 我们把具有共同因素的事物称为相关事物， 简称相关 。研究事物全体因素独立变化对事物状态影响的计算就称为 相关计算 。 数学多数情况下是在研究少数变量之间的变化关系，例如，函数（映射）、关系等，这主要基于实数的连续性。那种变量之间毫无瓜葛的纯离散型因素，除了逻辑代数，基本上很少研究。相关计算就是研究全体纯离散型的因素变化，如何对整体产生影响，其主要目标是研究独立的因素全体对整体的状态产生怎样的作用。 例如，基因对生物的影响，运动员对球队的影响，工程的各种基础设施对整个工程的影响，企业组织机构对企业的影响，系统输入对系统性能的影响，网络设施对网络的影响，基础教育对个人成才的影响，食物因素对生命进程的影响等。 相关计算用逻辑代数表达出来就是 SAT 问题。求 SAT 问题满足解就是相关计算的基本形式。子句就好比细胞，子句块就好比器官，任何一部分无解， SAT 都会无解。当然这些细胞或器官组织的不合逻辑相关，那么 SAT 也会无解。子句消去法可以准确地一次性求出 SAT 的满足解。因此，子句消去法是相关计算的基本方法。 一切带有概率方法的数学计算，都具有 NP 类问题的特征，只有子句消去法完全避开了 SAT 这个 NP 类问题的概率方法，直接一次性确定出 SAT 的满足解。这是从全局的角度研究因素，进行相关计算的基本方法。 子句消去法虽然是一个多项式时间复杂度的算法，但随着具体的 SAT 构成类型变化，有许多独特的快速的算法。例如， n 元逻辑变量为子句的 SAT ，就可以用反子句的概念在 O( n ) 时间复杂度求出满足解。 客观世界的相关计算问题不胜枚举，这种各自独立的因素全体的演化，是从整体的层次进行事物研究的必要方法。当事物因素十分庞大的时侯，穷举法是不能够在有限时间内完成任务的，只有子句消去法能够让我们快速地得到结果。 一种全面研究独立因素对事物影响的计算方法就此打开。我相信，相关计算会为数学计算开辟出一块全新的天地。让我们将这扇大门推得更开吧。 2016-11-16
深入研究子句消去法 姜咏江 多项式 C n k +C n k-1 +...+C n 1 +C n 0 与 2 n 相差多少？其实，只要 k=n ，那么前者就是后者。只有当 k 为常数的时侯，多项式与指数时间复杂度才有明显的时间效益。 k 为常整数，求由比 k 少的逻辑变量取值形成子句间与运算表达式结果为真值，就是 SAT 问题。如今 SAT 问题有了多项式时间复杂度的算法——子句消去法。但从多项式与 2 n 之间的关系来看，当 k 很大的时侯，算法执行的复杂程度（或则说任务量）也会很大，这就需要我们去寻找子句消去法能更快执行的方法。这里先介绍一个减少判断变量可选解的方法。 子句消去法最坏的情况是从头到尾判断的每个变量都出现两个可选解。如果能够有方法减少判断变量的数量，自然可以加快计算。 选判定理 ：子句块无唯一解变量，其非关联变量都有 2 个可选解。 证明 ：依据二进制限位数性质， k 阶子句块如果没有任何一个变量有 2 k-1 个表现值，那么至少有一对可以进入这个子句块的互反子句不在其中。由附件文中的定理 2 、 3 、 4 立即就可以得出此定理成立。 实际问题中的 SAT 问题，逻辑变量可能很多，而形成子句块共有的变量可能不多。在施行子句消去法求 SAT 解的过程中，先将各子句块中唯一解变量值确定，消去相关子句之后，剩下的都是无唯一解变量的子句块。此时只要去判断那些关联变量有几个可选解，就可以迅速地得出无解，或者求出 SAT 的满足解。 2016-11-12 附件： 子句消去法求k-SAT满足解（同行讨论稿）.pdf
姜咏江 SAT 的定义中是不允许出现重复子句的，但在子句消去的过程中，会出现降阶的子句块中有重复的子句。 t 阶子句块变量唯一解是因为它有 2 t-1 个相同的表现值（ 1 ≤ t ≤ k ）。在消去子句的过程中很难事前知道那些子句会重复，这样证明消去重复子句这一步算法时间复杂度为多项式时间就很困难。不过我们可以从总体上来探讨。 假如 SAT 子句的最高阶是 k ，那么子句块的总数不会超过 C n k +C n k-1 +...+C n 1 个。如此有 m 个变量表现值相同的子句块（ 1 ≤ m ≤ k-1 ）最多有 C n -m k-m +C n -m k-m-1 +...+C n -m 1 +1 个，那么有 m 个变量表现值相同的子句块的子句总数不会超过 C=2 k-m +2 k-m-1 +...+1 个。 C 是一个有限常数。因此，任何一个剩余的子句块的子句数数，都不会超过这个数。在小于常数 C 个数中，消去重复数的算法时间复杂度无疑是 O(1) 。而剩余子句块最多还是 C n k +C n k-1 +...+C n 1 个，所以 SAT 总体去掉子句块中重复子句的算法时间复杂度是 O( n k ) 。 2016-11-9
姜咏江 学术研究并不都需要秘密地进行，特别是那些所谓的世界难题一类，公开在科学网上研究论证，不怕讥笑和嘲讽，借助于批评者，能够获得快意和驱动力，激奋你快速前进。这是我两年多钻研子句消去法求解 SAT 问题满足解的特有体会。 两年中，我从无知 SAT 问题到有所收获，除了我自身的数学和计算机的功底之外，探索科学的强烈兴趣是我研究重要的动力。我将所有的不同见解作为参考，也作为鼓励自己前进动力的一部分，提醒自己，要善待或感谢那些嘲讽与讥笑，最后收获的将一定是由衷的快乐。 证明子句消去法是多项式时间算法确实很艰难。虽然我构造了子句块、关联段、变量可选解、降阶子句块等概念，并运用限位数理论解决了变量无解和唯一解形式的判断，以至于证明了每个变量都有 2 个可选解的 SAT ，都可以用子句消去法求出满足解，但证明子句消去法是多项式时间复杂度的算法仍然是艰难的。这种艰难源自于消去子句过程中，要删除子句块中的重复子句，或者要涉及到数排序。 大家知道， k-SAT 中 n 个变量的 k 个变量子句最多有 2 k C n k 个，去重复的过程中，子句数不会超过这个数，要用通常的去掉重复子句的方法，最坏大概要进行 2 k C n k 的阶乘次比较。显然，这不是一个多项式时间可以完成的问题。解决这个问题需要懂得计算机硬件设计方面的知识。设计一个带有存储单元空满标志的存储器，并实行数据标记单元存储法，这个问题就转化成多项式时间算法了！核心思想就是将二进制表示的子句，放到这个数为地址的存储单元（专家排序法 http://blog.sciencenet.cn/blog-340399-995138.html ）去掉重复，然后通过标志来选择操作这些数据。 SAT 问题不仅是一个数学和计算机软件程序设计的问题，它是一个用数学理论、计算机设计制作理论与方法的综合性问题。 限位数理论是我早年的研究， SAT 问题的解决中逼出来了专家排序法。不管今后这些方法会起到怎样的作用，作为一个凭借兴趣探讨学问的人都会有幸福感。公开搞学术的好处是可以借助别人的批评快速进步，最大的体会就是要经得起冷嘲热讽。 2016-11-5
姜咏江 用 n 个逻辑变量和其变量非形式中的不超过 k （ k 是一个常数）个，写出若干个或运算多项式（子句），问能不能设定这 n 个变量的一组值（是一个 n 位二进制数），使每一个多项式的逻辑值都是 1 （真）？这个问题就是被国外认定的世界难题 SAT 。 举个例子，有逻辑变量 x 1 , x 2 , … , x 5 ，它们的非形式是 x 1 ’, x 2 ’ , x 3 ’, x 4 ’, x 5 ’ ，随便写出的多项式有： x 1 ’+ x 2 ’+ x 3 ’+ x 4 ’+ x 5 ’ ， x 1 ’+ x 2 ’+ x 3 + x 4 + x 5 ’ ， x 1 + x 2 ’+ x 3 + x 4 ’+ x 5 ’ ， x 1 + x 2 + x 3 ’+ x 4 ’+ x 5 ’ ， 问是否能够将这几个多项式值都为 1 的那些二进制数找出来？ 这些多项式中都有变量的非项，可以马上找出 00000 可以满足要求。 如果上面的由 5 个变量及其非形式组成的多项式可能“残缺不全”，并且有很多个，你还能够一下子找出满足条件的二进制数吗？这个问题用穷举法可以办到，这需要将二进制数从 00000 一直到 11111 这 32 个数一一带入每个多项式验证。 n 个变量的这种验证次数总是 2 n 。 显然，当 n 较小的时侯，验证的工作量不大，但若 n 变大，而 k 不变的时侯，工作量就会以惊人的速度增大，以至于有上百个变量，而多项式并不太多的时侯，用计算机来验证也难以短时间内完成。 有 n 个变量的 SAT 如果有解，一定是在二进制数 0 ～ 2 n -1 之中。能不能根据多项式将这 2 n 个数中不是解或是解的单独找出来？这样在 n 位二进制数已知的情况下，速度会加快。 为了简单，我们用 1 表示多项式中的变量 x ，用 0 表示 x ’。那么每个多项式就可以写成二进制数的形式。如此我们就引进了子句块的概念，并且能够证明互反子句（二进制数表示的子句互为反码）都不在子句块中，都是 SAT 解的组成部分，有一个在子句块中，它的反子句就不是 SAT 解的组成部分。所谓子句块是相同变量组成的子句全体。子句是不是 SAT 解的组成部分，是由数码的位置来确定的。例如， 1 1 0 是 11100 、 10100 、 ... 、 11110 的组成部分，但不是 01100 的组成部分，虽然 110 在 01100 当中，这是因为 1 1 0 在 01100 对应位置数码不同。 我们能不能用带位置二进制数码表示的子句，找出 SAT 的全部解？这就是本文要谈的中心内容。 计算机中的数都是二进制数码表示的，同一数码在不同位置是它们的根本区别。 如果一组数码和一个子句块变量位置相对应，且能够使子句块中每一个子句的值为1，那么这组数码一定是 n 个变量SAT解的组成部分；如果这组数码虽然与子句块的变量的位置对应，但不能使这个子句块的所有子句值为1，那么这组数码对应所在的 n 位二进制数，一定不是 n 个变量SAT的解。 我们把二进制表示的子句所在n位二进制数叫子句的标志。根据子句消去法，SAT的解一定在子句标志当中。如果我们将SAT子句的所有标志，通过子句将其它们从 n 位二进制数中消去，那么剩下的 n 位二进制数就一定是由SAT中子句的反子句或不在SAT中的互反子句构成的。 在子句消去法中有一个很重要的定理： 反子句不在和互反子句都不在子句块中的子句是该子句块的解 。 根据这一定理，将剩下的 n 位二进制数取反，得到的数一定都是SAT的解。 如果你对 SAT 有所了解，或者看过我的子句消去法，我想理解上面的叙述不会有问题。问题会在这一过程中的算法，是不是多项式时间复杂度？ 假如 SAT 中最高阶子句有 k 个变量，那么 SAT 最多有2 k C n k +2 k-1 C n k-1 +...+2C n 1 这 k 次多项式计算结果个子句。我们可以先从低阶子句开始消去子句标志，那么最多也就是要进行 2 k C n k +2 k-1 C n k-1 +...+2C n 1 次（实际上，由于高阶子句包含低阶子句，这种操作要少得多）就可以完成子句标志消去的工作，剩下的 n 位数的反码就都是 SAT 的解！可见整个 子句标志消去法 的算法时间复杂度为 O( n k ) 。 需要说明，在计算机中 0 ～ 2 n -1 个二进制数是放在文件中，或地址编码本身，计算机中只有二进制数，因而寻找子句的标志可以用一个指令实现。由此可见，由子句消去其标志就是一个 O(1) 时间复杂度。 以上我谈的问题是计算机理论和方法中的问题，搞计算机理论的人都可以鉴定对与错，没有必要非要请“洋专家”评判。 请参阅： http://blog.sciencenet.cn/blog-340399-1009188.html http://blog.sciencenet.cn/blog-340399-1009397.html http://blog.sciencenet.cn/blog-340399-987007.html 2016-10-31
SAT 无满足解的充分必要条件 姜咏江 本人发明的子句消去法，是快速求出 SAT 满足解的方法。该方法无疑在电子电路设计的化简和优化中会起到十分重要的作用。关于子句消去法的原理和方法，请参阅： http://blog.sciencenet.cn/blog-340399-961507.html 。 SAT 的满足解是由 n 元逻辑变量的一组值构成的，这组由数码 0 和 1 构成的数组带入 SAT 表达式，会使 SAT 表达式的值为 1 。在子句消去法中， SAT 满足解体现为所有的子句都能在值为 1 的情况下消去，最终没有剩余子句。 不论 SAT 还是 k-SAT 一般情况下常有多解，因而研究它们的无解情况甚至比有解都要重要。本文主要给出 SAT 无满足解的充分必要条件。 基本定理 ： SAT 无满足解的充分必要条件是子句块或动态块无解。 子句块由共同变量的子句构成，而动态块是由设定一些变量值后的具有共同变量的剩余子句构成。因而容易理解子句块或动态块无解，肯定 SAT 无满足解。 证明 ：【充分性】依据子句消去法，当有子句块或动态子句块无解时，就会有子句不能消去。可见充分性成立。 【必要性】若 SAT 任意子句块或动态子句块都有解，则知所有的变量都有确定的值可一起构成 SAT 满足解。必要性成立。 2016-3-27
目前为止，我们直接针对NP的流行定义：“NP是多项式时间可验证的问题”，解读其认知错误。我们指出，此认知错误来自于混淆了“nondeterministic Turing machine”二个不同的内涵：NTM（非图灵机）和NDTM（不确定性图灵机），从而得出NP二个定义等价，致NP的“不确定性”消失。 另外，还存在着一个更加令人困惑的流行观点：NP是可计算的，理由是，NP存在指数时间复杂度算法。 我们在博文“什么是‘判定问题’？（1）－可计算性理论与计算复杂性理论”（ http://blog.sciencenet.cn/home.php?mod=spaceuid=2322490do=blogid=895834 ）中，简单回顾了算法理论的历史，指出：此观念直接导致计算复杂性理论（Computational complexity theory）与可计算性理论（Computability theory）相分离的现状，使作为计算复杂性理论基础的NP完备理论（NP－completeness theory），成了无源之水，无本之木！ 这里，我们希望解读“NP存在指数时间算法”的意义，由此出发逐步解读“NP是可计算的”，为此，我们借用具有代表性的“SAT问题”来帮助解读。 SAT问题，是“布尔逻辑可满足性问题（boolean SATisfiability problem）”的简称，指给定一个合取范式的布尔公式，判断其是否可满足。SAT问题是逻辑学的一个基本问题，也是算法理论的核心问题，因为任何一个欲通过算法求解的问题（P和NP）都可表达为SAT问题：2-SAT是P问题（确定性问题）的代表；3-SAT是NP问题（不确定性问题）的代表。 然而SAT问题与P和NP的关系，学术界一般用所谓的“归约（reduction）”来阐释，即将SAT问题与P和NP相互表达，但是于认知问题的角度，此“归约”只是停留在问题的表面，并未深入问题的本质，就好比问“老王在哪里”，却被告知“老王在老张的隔壁”，而老张比老王更难找，因为还不认识老张。 所以，我们希望通过对SAT问题本身作些必要的解读，来帮助认知P和NP。我们先阐释“问题”、“实例”与“解”的层次表达，并用哈密顿路径问题表达为SAT问题的案例说明之： 一，“问题”、“实例”与“解”的层次表达 “问题（problem）”、“实例（instance）”和“解（solution）”是算法理论中最基本的概念，只是对这些概念的解释一般未作层次的分辨（见附录）。 从日常语言的角度，“问题”指：对事物，问是否具有某种“性质”。 从算法语言的角度，“问题”指：对任何一个问题实例，问是否存在具有某种性质的“解”；“性质”指约束条件，“解”指满足约束条件的结构。“问题”与“实例”相对而言，“问题”是“实例”的抽象形式。 从逻辑语言的角度，一个约束条件可表达为“子句”，子句Ci（1≤i≤m）是文字的析取式：l1∨l2∨…∨lk，文字li（1≤i≤k）为某一布尔变量或该布尔变量的非；若干约束条件可表达为诸子句的合取式F：C1∧C2∧…∧Cm，即合取范式。合取范式F表达“解”的结构，SAT问题（也称合取范式的可满足问题）指：问是否存在一组布尔变量的赋值（解），使得整个合取范式F取值为真？ 于是，一个欲通过算法求解的问题表达成了SAT问题，正是在此意义上，SAT问题在算法理论和问题求解中都占有重要地位。 二，案例：哈密顿路径问题表达为SAT问题 我们以哈密顿路径问题为例（见博文“参详P与NP的二个实例“－ http://blog.sciencenet.cn/blog-2322490-878672.html ）： 问题：任给一个有向图G及二个结点s和t，问在G中是否存在一条从s到t且遍历G的所有结点的路径（哈密顿路径）？ 实例：如图1，来自Sipser的书。 通过表达哈密顿路径所须满足的约束条件，把哈密顿路径问题表达为SAT问题，其步骤如下（并用实例图1说明之）： 1，定义布尔变量 xij = 1，哈密顿路径中第i位子是结点j xij = 0，哈密顿路径中第i位子不是结点j 哈密顿路径中有n个位置，故每个结点有n个布尔变量，共有n＊n布尔变量： 2，定义字句 （1）每个结点j只能在哈密顿路径中出现一次 x1j ∨x2j ∨···∨xnj ¬xij ∨ ¬xkj ， i ̸= k 比如，结点1只能在哈密顿路径中出现一次： x11 v x21 v x31 v x41 v x51 v x61 v x71v x81 ¬xi1 v ¬xk1 ， i ̸= k （2）哈密顿路径中的每个位置i只能有一个结点 xi1 ∨xi2 ∨···∨xin ¬xij ∨ ¬xik， j ̸= k 比如，位置1只能有一个结点： x11 v x12 v x13 v x14 v x15 v x16 v x17 v x18 ¬x1j v ¬x1k ， j ̸= k （3）不是相邻的二个结点不能在哈密顿路径中相邻出现 ¬xki ∨¬x(k+1)j， (i,j） ̸∈G，k=1,2,...,n−1 比如，结点1，4不能在哈密顿路径中出现： ¬xk1 ∨¬x(k+1)4， (1,4） ̸∈G，k=1,2,...,n−1 3，定义合取范式公式 F由上述子句的合取式构成。 4，定义SAT问题 任给一个合取范式F，问是否存在一组布尔变量的赋值，使得F取值为真？ 于此实例，F是可满足的，比如，x11=true, x23=true, x35=true, x44=true，x52=true，x66=true，x77=true，x88=true，令其余布尔变量为false，此组变量赋值使F＝true，代表哈密顿路径：1－3－5－4－2－6－7－8。 ＊＊＊＊＊＊ 附录： 1，在Garey，Johnson的书（Computers and Intractability - A guide to the Theory of NP-Completeness）中第一章的第二节（p.4）： 1.2 Problems, Algorithms, and Complexity Let us begin with the notion of a problem. For our purposes, a problem will be a general question to be answered, usually possessing several parameters, or free variables, whose values are left unspecified. A problem is described by giving : (1) a general description of all its parameters, and (2) a statement of what properties the answer, or solution, is required to satisfy. An instance of a problem is obtained by specifying particular values for all the problem parameters. As an example, consider the classical traveling salesman problem. The parameters of this problem consists of a finite set C = {c1, c2, …, cm} of cities and, for each pair of cities ci,cj in C, the distance d(ci,cj) between them. A solution is a tour of minimum length. One instance of the traveling salesman problem, illustrated in Figure 1.1, is given by C={c1,c2,c3,c4}, d(c1,c2)=10, d(c1,c3)=5, d(c1,c4)=9, d(c2,c3)=6, d(c2,c4)=9, and d(c3,c4)=3. The ordering c1,c2,c4,c3 is a solution for this instance, as the corresponding tour has the minimum possible tour length of 27. 2，维基网（https://en.wikipedia.org/wiki/Computational_complexity_theory）： Problem instances A computational problem can be viewed as an infinite collection of instances together with a solution for every instance. The input string for a computational problem is referred to as a problem instance, and should not be confused with the problem itself. In computational complexity theory, a problem refers to the abstract question to be solved. In contrast, an instance of this problem is a rather concrete utterance, which can serve as the input for a decision problem. For example, consider the problem of primality testing. The instance is a number (e.g. 15) and the solution is yes if the number is prime and no otherwise (in this case no). Stated another way, the instance is a particular input to the problem, and the solution is the output corresponding to the given input. To further highlight the difference between a problem and an instance, consider the following instance of the decision version of the traveling salesman problem: Is there a route of at most 2000 kilometers passing through all of Germany's 15 largest cities? The quantitative answer to this particular problem instance is of little use for solving other instances of the problem, such as asking for a round trip through all sites in Milan whose total length is at most 10 km. For this reason, complexity theory addresses computational problems and not particular problem instances.
标签: SAT问题
