多项式时间复杂度和指数时间复杂度相差多少？ 姜咏江 如果以问题条件中对象数量 n 做为考察标准，随着 n 的增大，什么样的算法耗时增长速度快？这就是解题当中的时间复杂度问题。同一个问题，寻找耗时增长速度最慢的算法，无疑具有十分重要的意义。 从数学知识知道，一次函数 y=a n +b 随着 n 的变大， y 的增长速度是不变的。还知道， k和c是大于1的正 常整数时， y =a 0 n 0 +a 1 n 1 +...+a k n k 和 z =a 0 c 0 +a 1 c 1 +...+a n -1 c n -1 +a n k n 比较，当 n 大到一定程度后， z 的增长速度要比 y 快得多。 y 的表达式称为多项式型， z 的表达式称为指数型。 在计算机编程的算法中，如果对 n 的重复操作是可以用多项式型计算，避开指数型无疑是人们所希望的。在计算机中对 n 的重复操作是可以用多项式型计算就是多项式时间复杂度 O( n k ) ，用指数型计算的过程，就是指数时间复杂度 O(c n ) 。有许多实际问题，人们只是找到了指数型的算法，没有找到多项式型算法。对于后者能否找到多项式型算法的研究成为了世界难题，这就是 P 与 NP 问题。 指数型最简单的是 z =2 n 。我这里就举求集合子集的例子，来说明这两者的关系。 A. 求 n 个元素集合的全部子集数。 用元素添加法知，包括空集有 C n 0 +C n 1 +...+C n n =2 n . B. 求 n 个元素集合的不超过 3 个元素的子集数。 包括空集有 C n 0 +C n 1 +...+C n 3 . 由此可见多项式型和指数型之间的关系。多项式型的幂指数一定是不超过一个常数，这是二者区别的关键。在 n 增大的时侯， k 是不能够也跟着 n 增大。很多人混淆了这种约定，因而陷入了无法自拔的境地。 不可否认，多项式型在 k 相当大的时侯，随着 n 的增大，用计算机计算仍然耗时庞大，但与指数型最小的 2 n 比起来也会是“小巫见大巫”。 证明 C n 0 +C n 1 +...+C n n =2 n 如下： 添右定理 ： n 元集合用添右组合法得到全部非空子集为 2 n -1 个。 这个定理需要证明全部非空子集不少，且都不相同。 这里用归纳法来证明。 设 n=2 ，那么 A= ｛ a 1 ,a 2 ｝，则 A 的转移组合得到的子集为｛ a 1 ｝｛ a 2 ｝｛ a 1 ,a 2 ｝子集数为 2 2 -1=3 说明子集数正好且不重复。 设 n=k 时得到的子集｛ a 1 ｝｛ a 2 ｝ ... ｛ a 1 ,a 2 ,...,a k ｝满足条件子集数为 2 k -1 ，且不重复。那么当 n=k+1 时，则除添加子集｛ a k+1 ｝之外，需要将 n=k 时得到 2 k -1 个子集全部添加 a k+1 ，形成的全部子集为 ｛ a 1 ｝｛ a2 ｝ ... ｛ a k ｝｛ a k+1 ｝ ... ｛ a 1 ,a 2 ,...,a k ｝｛ a 1 ,a 2 ,...,a k ,a k+1 ｝ 子集总数应为 2 k -1+2 k =2 × 2 k -1=2 k+1 -1, 说明子集总数正确。 假设 n=k+1 时出现了重复子集，不妨设有子集 B i =B j ， i ≠ j ，它们之中都包含 a k+1 。那么将 a k+1 从它们之中取出，则应有 B i \ ｛ a k+1 ｝ =B j \ ｛ a k+1 ｝，这与 n=k 时得到的子集不重复子集矛盾。故没有重复子集产生。 证毕。 2016-12-1
姜咏江 消去块中唯一解， 不然找一可选解， 解多暂时一边放， 全多选解可得解。 《时间复杂度解释： 子句块变量唯一解的判断条件为有2 k-1 个0或1，如果同时0和1都有2 k-1 个SAT无解 。 SAT 的子句块最多有 2 k C n k +2 k-1 C n k-2 +…+ C n 1 这多项式个，子句块变量最多为 k 个， k 是一个常数，子句块可能重复的子句不会超过 2 k-1 C n k-2 +…+ C n 1 个，所以对子句块去掉重复子句的操作不会超过一个常数，知时间复杂度总是 O （ 1 ）。这样，对 SAT 全体子句块去重复子句的操作时间复杂度就是多项式 O( n k ) 。 可选解通过设定变量值，然后施行子句消去法，到关联剩余子句块全多解或关联段边界。 这一过程最多有可能进行 2 k C n k +2 k-1 C n k-2 +…+ C n 1 个子句块消去操作，最坏每个变量操作 2 次， n 个变量操作时间复杂度就是 O( n k+1 ) 。 只要是变量全多可选解，那么可一次求出满足解。 这有定理保证。 结论：子句消去法时间复杂度不超过O( n k+1 )。 》 2016-11-8
姜咏江 学术研究并不都需要秘密地进行，特别是那些所谓的世界难题一类，公开在科学网上研究论证，不怕讥笑和嘲讽，借助于批评者，能够获得快意和驱动力，激奋你快速前进。这是我两年多钻研子句消去法求解 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
组合数 C n n-k 是不是多项式？ 姜咏江 在 P/NP 的问题中，多项式的概念成为了探讨 P 是否等于 NP 问题的关键。关于多项式我在博文《关于多项式时间的辨析》 http://blog.sciencenet.cn/blog-340399-895336.html 、《算法多项式时间复杂度不靠谱的证明》 http://blog.sciencenet.cn/blog-340399-898296.html 、《有限元线性过程计数原理》 http://blog.sciencenet.cn/blog-340399-896333.html 和《算法多项式时间复杂度是天大的笑话！》 http://blog.sciencenet.cn/blog-340399-895858.html 当中提出了自己的看法，并提出了从等式 2 n = 来看，所谓 O( n k ) 的多项式时间是一个悖论。 从组合数计数公式 C n k =n(n-1)(n-2)…(n-k+1)/k! 来看，这是一个 k 次多项式，其中 k ≤ n 。在此等式中总有 C n k =C n n-k 这个相等的关系式，那么我们不禁要问：“ C n n-k 是不是多项式？” 多项式有一个很重要的性质：任何有限个多项式之和都是多项式。 我用组合多项式的方式求出了 n 个数的全部子集，并且求出了任何子集的和（请见博文 http://blog.sciencenet.cn/blog-340399-849597.html ）。如果你承认了求子集和的这一过程是多项式过程，那么 2 n 不是多项式就成了错误的认识；如果你不承认这是一个多项式过程，那么“任何有限个多项式之和都是多项式”这个性质也就不存在了，也就是说所谓的多项式概念也不存在了。这不是个悖论吗？ 归根结底，我们要回答 C n n-k 是不是多项式？ 2015-8-26
关于多项式时间的辨析 姜咏江 在 P/NP 的问题中，不论是通俗的定义还是在形式语言的定义中，都将所谓的多项式时间做为重要的基础概念。什么是多项式时间？本文从计算机程序执行时间计算的角度出发，给出了程序执行时间计算的基本公式，并在该公式的基础上进行所谓多项式时间辨析。 1. 什么是多项式？ 在数学中人们将 形式的表达式一般称为多项式，其中 x 是变量， n 是某一个确定的自然数， a i 是第 i 项的系数。从函数的观点看有函数 f ( x ) = 。其实，多项式的项是一种乘积的形式，而将多个乘积的表达式用加号连接起来，就得到了一个多项式。为此多项式还有函数 g ( x ) = ，它的右侧表达式又可以叫指数多项式；如果将幂底数和幂指数都认定是变量，那么就有二元函数 j ( x , y ) = ，右面的表达式又叫幂多项式。 2. 如何理解计算机程序执行时间计算？ 众所周知，计算机是靠主频的时钟周期来划分时间单位的。一个时钟周期决定着计算机的一个基本状态。算法程序执行时间完全可以用其消耗的主频时钟周期计算出来。图灵机并没有这种实际严格的时间计算，但我们可以认为图灵机的每一次状态变换都需要一个统一的固定时间，这样就可以在假定时间单位下讨论时间消耗多少的问题了。 不论图灵机还是只有一个处理器的计算机，它们都遵循着线性顺序处理方式的特点来进行动作，因而计算算法程序执行的时间消耗，必然要遵从线性顺序处理方式的计算方法。这就是说计算机从程序启动的时刻起，所有的计时应为基本动作时间的总和，最终都可以用一个自然数来表示某种单位时间。 在这个数学计量过程中，可以依据某种条件来划分出计量的分段，这种分段我们称之为计量段。任何一个计量段都是有限的，而且最多只能进行有限次重复计量，不然就无法得到任何有效的计量结果。 如果某计量段的一次计量用自然数 n 表示，而有限重复的次数用 c 来表示，那么这段线性计量值就可以用 c × n 表示。当重复次数 c 恰好等于 n 的时候，就可以出现 n × n=n 2 的情况。如果重复次数恰好为 c=a × n k-1 的形式（ a 是一个不等于 n 的数， k 是一个自然数），那么计量的表达式中就会出现 c × n=a × n k-1 × n=an k 这种表达式。如果我们探讨的是多个不同计量段的情况，就会出现 （ ij ） 的计算公式，其中 n 和 k 是幂底数和幂指数中的最大数， a ij 称为系数 。我们称公式（ ij ）为幂多项式。 幂多项式（ ij ）只有在极特殊的情况下才会成为幂底数 n 是一个变量 x ，最高幂指数 k 为常数的所谓“多项式”，此时公式（ ij ）就成为了 ；而当幂底数 n 为常数，幂指数 k 为变量 x 的时候，才能使（ ij ）成为所谓的“指数多项式”，那么公式（ ij ）就成为了 的形式 。 算法是程序设计的方法。一种算法客观上就规定了一个计算机程序执行的顺序，从前面谈到的时间计算来看，就成了一种划分时间段及重复计量的一种方法。 3. 程序执行时间都可以表达成幂多项式 在图灵机或现代计算机上，任何有解算法程序执行时间，不论如何，总能够用一个自然数表达出来，不然就与算法程序有解相悖。尽管有些问题的算法完成执行过程，恐怕要用人类都无法等待的时间才能完成，但聪明的人类可以不用等到那个结束的时候，而是采用数学方法计算出计算机能够解决这个问题所用的时间。因而研究计算算法执行时间具有十分重要的实际意义。 我们从计算机线性动作的基本方式出发，一般性地讨论了算法程序执行时间计算的基本形式（ ij ），但这个表达式似乎对我们过于抽象。能不能从算法的角度说明（ ij ）公式中各个标识符所表达的实际意义？过去，许多人认为不可能确切地计算出程序执行的时间，其实这是完全可以办到的事情。 从计算机程序设计的基本结构来看，任何程序不外乎有顺序、分支、循环和子程序调用这四种基本结构。分支是有选择的顺序，而子程序可以镶嵌到调用点，使其变为顺序。这样一来，所有的程序都可以转化成顺序、分支和循环这三种基本结构。 虽然在算法设计当中有这三种基本结构，但在一个处理器上，算法程序实际执行中，一律都必须转化成一维线性有序执行的方式，即以机器基本动作的先后方式完成程序执行。这种执行方式可以通过（ ij ）幂多项式来计算基本动作的发生次数，其中 n 是多层循环结构的第 n 层循环次数， k 是循环嵌套层数， a nk 是循环体基本动作单位数。 如果我们更一般化地考虑基本动作单位是什么？那么可以认为在图灵机上就是一次状态转移，在现代计算机上就是一条机器微指令，在一般编程语言中，就认为是一个语句。在一般性编程语言中，虽然每个语句执行的时间不同，但这并不失问题探讨的一般性，因而我们仍然可以假定它们执行的时间相同。 4. 相关讨论 算法程序执行时间的计算无疑是关系到算法时间复杂度的决定因素。有关算法程序执行时间是由指令（基本动作）重复执行次数的多少来决定的，而指令重复执行次数又是由程序结构的循环层数 k 、层内循环次数 n 和各层内部指令数 a 三个量所确定。有关对算法时间复杂度的辨析，我们将放到另外的篇幅中讨论。 2015-06-03
P 与 NP 问题是让聪明人做傻事 姜咏江 世界上的事情有难有易，这是人们都知道的常识。然而就是被称为世界上的聪明人常常做傻事。上中学时听说过：牛顿在门上挖一个大洞和一个小洞，为的是让小猫走小洞，大猫走大洞。这事真假且不论，反映出聪明的科学家也可能办傻事。 千禧大奖的头号世界难题， P/NP 问题就是一个让聪明人办傻事的闹剧。为什么？这事是让人们将所有的复杂的事情都去找简单的方法解决同一件事情的全部结果混为了一谈。 我以解决任意 N 个数的子集和问题为例，就可以说明这种混淆给人们带来的艰苦劳动是多么的不值得。 N 个元素集合每增加一个元素，那么就要增加 2 N 个子集，这就是说在不知道子集都是什么的情况下，需要以指数运算的方式来求这些子集，这在算法执行中自然要消耗大量的时间。如果我们将这一过程做为查找某个满足条件的子集是否存在（ yes/no 问题），那么就不可能是一种较快执行的算法。如果我们在 N 个元素集合的所有子集都存在的情况下，去回答某个满足条件的子集是否存在的 yes/no 问题，我们只要用查询的方法就可以完成，也就是说我们可以用 O （ n ）的所谓多项式时间复杂度解决问题，也就可以得出 P=NP 的结论。 因为求子集的算法是一个指数型运算过程，这个问题不可能用 n k 形式的算法（ k 是常数）求解全部子集。即使某个曾经认为复杂的问题能够用简单的函数问题求解，也不代表能够将所有复杂的问题都可以用简单的固定多项式函数方式得到 yes/no 问题的回答。 我在这里规劝那些科学界的聪明人莫要再为这种傻事浪费时间了。请参考 http://blog.sciencenet.cn/blog-340399-849311.html http://blog.sciencenet.cn/blog-340399-861142.html 2015-5-1
程序执行时间计算 姜咏江 简介 ： 算法时间复杂度的研究，以所谓的多项式时间做为最低复杂度，实在有些不靠谱。计算机程序执行时间可以用其编译之后的机器语言程序来计算。因为每一机器指令（汇编指令）的指令周期都是确定的，故计算程序执行时间，可先计算出每条机器指令重复执行次数，然后与指令周期相乘求和，最终获得准确时间。本文提出的算法程序执行耗时计算，要以指令重复执行次数为基础，给出了指令重复执行次数的基本计算公式。 1. 背景 为了研究算法程序完成任务运行时间长短，人们引入了算法时间复杂度的概念。 在维基百科中，算法时间复杂度被定义为： 在 计算机科学 中， 算法 的时间复杂度是一个 函数 ，它定量描述了该算法的运行时间。这是一个关于代表算法输入值的 字符串 的长度的函数。时间复杂度常用 大 O 符号 表述，不包括这个函数的低阶项和首项系数。 在百度文库中有计算方法解释：一般情况下， 算法 的基本操作重复执行的次数是模块 n 的某一个函数 f (n) ，因此，算法的 时间复杂度 记做： T(n)=O( f (n)) 。若 T(n)/f(n) 求极限可得到一常数 c ，则 时间复杂度 T(n) = O(f(n)) 。 不论维基百科还是百度的解释，都称算法时间复杂度是程序运行时间的定量描述。实际上，我们见到的 大 O 符号 表述只能算定性描述，根本谈不上定量。 为了能够确实对算法程序运行时间进行定量分析，本文从单处理器计算机指令设计与程序执行的原理出发，依据程序设计的基本结构，提出了一种比较切合实际的程序执行时间计算方法。结果会见到有限程序运行时间的计算，都可以表达成一种多项式形式。 2. 指令重复执行次数 我们知道，不论任何形式的计算机设计语言程序都要转化成机器语言程序才能够执行。因此，用与机器语言一一对应的汇编语言来讨论程序执行时间才应该是最准确的。不过由于各种语言程序在执行时间分析上具有一定的一致性，故而作定性分析时，也可以替代汇编语言。 不论何种计算机程序设计语言，就程序设计的基本结构来说都是一致的。程序的基本结构分为：顺序、分支、循环和子程序调用。任何计算机程序的执行都可以说是这几种程序结构的重复，所以计算程序执行过程所消耗的时间，都离不开对程序基本结构的分析。 程序执行的过程是由每个指令执行的过程组成的，因而程序执行的时间就是指令执行时间的累加。在汇编程序语言中，每条指令执行的时间消耗是确定的。特别是那些指令周期相等的计算机系统设计，用单一指令执行的时间乘以全部指令重复执行的次数，就能够计算出程序执行所需要的时间。如果计算机的指令周期不相同，则可以用每条指令的指令周期做为系数，进行所谓的加权求和来计算程序执行的时间。因此，算法程序执行时间的消耗，最关键的是计算出每条指令重复执行的次数。 3. 指令重复执行次数公式 我们将汇编程序不在执行状态的每条指令叫“写出的指令”，计算指令重复执行次数，就与这种写出的指令有关。 指令重复执行次数是由程序的基本结构所决定的。在顺序程序结构中写出的指令重复执行次数是 1 。而在循环结构中，写出的指令重复执行次数与循环的次数一致。程序执行中消耗时间最长的就是循环程序结构。直观地说，循环的次数越多，处在循环体内的写出指令重复执行次数越多，因而累计耗时就越长。在此种观点之下，整个程序就可以看成是多层循环结构，可以按照多层循环结构来计算程序执行时间。当然，子程序可以单独计算子程序执行的时间。由于分支程序结构的程序分支选择总是惟一的，故时间计算基本上等同于顺序结构。 我们将顺序与分支都认定为 0 层循环，那么程序运行的耗时计算，可以建立在多层循环结构的耗时计算上，也就是循环结构的写出指令重复执行次数计算上。如果用函数来描述，那么一个程序的指令重复执行次数 T 应为层内循环次数 n 与循环层数 k 的二元函数，即 T = f ( n , k ) 。为说明问题简单通俗，我们通过 c 程序的例子加以解释。 例 1 ，假设 n=k ，那么幂 n n 结构的 n 重循环用 c 语言描述如下。 for( i 1 =1; i 0 =n; i 1 ++){ for( i 2 =1; i 1 =n; i 2 ++){ ...... for( i n =1; i n =n; i n ++){ no 1 += 1; no 2 += no 1 ; }}...} for 语句条件表达式的初值语句在每层只执行一次，而定界和步长语句都要执行 n 次。显然最内层每个语句重复循环次数是 n n ，向外各层依次为 n n-1 、 n n-2 、 … 、 n 2 、 n 。那么总的语句重复执行次数为 1+3n+3n 2 +3n 3 +…+3n n-2 +3n n-1 +4n n 。 对于一个程序， 在顺序结构中，指令重复执行次数是 1 ；在单层 n 次循环结构中，指令重复执行的次数是 n ；在 k 层 n 次循环当中写出的指令，其重复执行的次数是 n k 。于是各层指令重复执行的次数可用公式 f ( n , k ) = a 0 +a 1 n +a 2 n 2 +...+a k -1 n k -1 +a k n k （ 1 ） 来计算，其中 a i 是各循环层的写出指令数， i=0,1,2,...,k 。 如果将公式（ 1 ）的 k 认为是常量，那么（ 1 ）式不就是一个多项式吗？我们能说这种形式的算法复杂度程序执行最快吗？ 4. 计算类型实例 公式（ 1 ）中，若幂指数最高固定为常数 k ，则得到 k 次多项式；若幂底数固定为常数 k ，则得到指数多项式；若 1 层循环次数从 1 开始，逐层循环次数加 1 递增，则得到阶乘多项式。如此变化循环层数或循环次数，则可以得到各种重复执行计算的实际公式。为了说明这方面的演变，我们再举两个实例。 例 2 ，将（ 1 ）式的幂底数（循环次数）设定为常数 2 ，则能够得到指数型指令重复执行的多项式表达式 a 0 +a 1 2+a 2 2 2 +...+a n-1 2 n-1 +a n 2 n 。 例 3 ，设定幂底数是常数 k ，下面的循环结构可以实现 nlog k n 型的指令重复执行次数。 for( i=0; in; i++){ for( j=k; j=n; j*=k){ no 1 += 1; no 2 += no 1 ; }} 由 j*=k 知 j 的值循环变化序列为 k,k 2 ,k 3 ,..., k t =n ，于是内层循环次数 t=log k n 。 由于这个程序的外层循环次数是 n ，内层循环次数是 log k n ，因而程序指令重复执行次数总共是 1+2n+n+4n log k n=1+3n+4n log k n 。 5. 程序执行时间比较 关于算法程序时间复杂度，一种流行的观点认为多项式类型的算法复杂度较低，而且认为多项式类型算法程序运行耗时最少。其实这是一种错觉。 从公式（ 1 ）我们知道，决定算法程序执行时间长短的有两个因素，一个是多项式的幂指数 k ，另一个是多项式的幂底数 n 。当幂指数 k 较大的时候，虽然它是一个常数，我们也不能够认为多项式时间类型算法程序运行时间消耗会最少。特别在 nk 时，从（ 1 ）式立即知道， n k 多项式型算法程序时间的消耗会大于幂 n n 型算法程序的耗时。这说明在较大的循环层数的范围内，不能够就认为多项式时间具有较低的复杂度，当然也不能够认为这种情况的算法程序耗时最短。我们不妨仅就一项来进行比较。 例如设 n=5 ， k=7 ，那么 n k =5 7 =78125 ；而 n n =5 5 =3125 。由此可见用多项式时间复杂度来说明算法程序耗时长短是不靠谱的事情。有人也许会说， n 趋于无穷才对。想象一下， n 趋于无穷大对程序执行的时间计算的意义有多大？ 6. 结论 计算程序执行时间，要通过程序写出的指令重复执行次数进行，指令重复执行次数的多少，取决于程序循环结构的循环次数和循环层数这两个变量。通俗地讲，循环层数和循环次数越大，程序运行得出结果所消耗的时间越长。 任何在计算机上完成任务的程序运行，都需要在有限时间内解决问题，不然我们编写的程序就失去了意义。因而研究程序运行时间的有限性，远比研究程序执行时间的无限性更为重要。用算法程序执行中的指令重复执行次数来计算程序运行时间，是一种精确实用的计算方法。 同一任务的算法不同，会产生程序执行时间的很大差异，与此有关的内容是属于最优算法研究的问题，但不是所谓“多项式时间复杂度”就能解决的问题。 Email accsys@126.com 2015-01-10
标签: 多项式时间
