Algorithm ZJXQF for SAT Problem Author:JIANG Yong-jiang Input : A “0” and “1” table of clauses Q. Output: A Truth Value. Function ZJXQF(Q) (1). If a variable has 2 k -1 “0” and “1” in a k -block ( k =1,2,3,…, j, j is a constant number) Thenreturn “false”; (2). If a variable has unique solution in a clause block Then delete the variable and the relative clauses in Q,call (1); (3). If a variable has unique solution in a relative section Then delete the variable and relative clauses in Q,call (2); (4). Final, set 0 (or 1) to a selected variable in the possible solutions table and delete the line by relative clauses; (5). By relative value and extend the solution, can get the result. This polynomial algorithm is a completed for solve any SAT problem. I have the program for test. If you want get it, I will give you the program and the Eliminate-Clause method paper. MyEmail: accsysuibe@uibe.edu.cn 2017/5/16
Alan Cobham（1927－2011）在1965年的文章“The Intrinsic Computational Difficulty of Functions”中最早提出“多项式时间复杂度问题类P”，Cook在其1971年的著名论文“The complexity of theorem proving procedures”中引用，被认为是计算复杂性理论的重要论文之一，由此有所谓的“Cobham论题”（ https://en.wikipedia.org/wiki/Cobham%27s_thesis ）： Cobham's thesis, also known as Cobham–Edmonds thesis asserts that computational problems can be feasibly computed on some computational device only if they can be computed in polynomial time; that is, if they lie in the complexity class P. Formally, to say that a problem can be solved in polynomial time is to say that there exists an algorithm that, given an n-bit instance of the problem as input, can produce a solution in time O(n^c), where c is a constant that depends on the problem but not the particular instance of the problem. 上述文章是Cobham在1964年的“International Congress for Logic, Methodology, and the Philosophy of Science”大会发言，他以“乘法比加法难吗？”问题开头： －The subject of my talk is perhaps most directly indicated by simply asking two questions: first, is it harder to multiply than to add? and second, why? 接着他提出“元数字分析（metanumerical-analysis）”，表明此方法用于分析独立于任何具体的计算方法的问题： － So in metanumerical-analysis we encounter problems related to specific computational systems or categories of computing machines as well as problems such as those mentioned above which, though concerned with computation, are independent of any particular method of computation. Cobham从“Grzegorczyk层次”出发（ https://en.wikipedia.org/wiki/Grzegorczyk_hierarchy ），Grzegorczyk层次是对原始递归函数的分类： S^0 includes functions such as x+1, x+2,… S^1 includes functions such as x+y, 4x,… S^2 includes functions such as xy, x^4,… S^3 includes functions such as x^y, 2^2^2^x,… 。。。 Cobham将递归函数与计算复杂性相联系，提出时间复杂度TIME(n)和空间复杂度SPACE(n)： －With each single-tape Turing machine Z which computers a function of one variable we may associate two functions, TIME(n) and SPACE(n). Assuming some standard encoding of natural numbers - we might take decimal notation to be specific - we define TIME(n), where n is a natural number, to be the number of steps (instruction executions) in the computation on Z starting with n encoded on its tape, and define SPACE(n) to be the number of distinct tape squares scanned during the course of this computation. Cobham通过一个定理指出：指数形式的函数（S^k，k=3）具有指数形式的时间复杂度和空间复杂度后，就集中在讨论具有多项式形式的函数集合（S^2）： －This leaves us some latitude for differentiating among functions in S^2. The closest analog of the foregoing theorem concerning TIME(n), rather than SPACE(n), that I know of states that for any f in S^2 there exists a Turing machine Z which computes it and such that TIME(n) is bounded by a polynomial in its argument. 最后，Cobham提出了“多项式时间复杂度问题类P”的概念： - We find that it makes a definite difference what class of computational methods and devices we consider in our attempt to formalize the definition （of a feasibly computable function）. … The problem is reminiscent of, and obviously closely related to, that of the formalization of the notion of « effectiveness ». But the emphasis is different in that the physical aspects of the computation process are here of predominant concerne. The question of what may legitimately be considered to constitute a step of a computation is quite unlike that of what constitutes an effective operation … If we are to make fine distinctions, say between and , then we must have an equally fine analysis of all phases of the computational process… We must be prepared to argue that we haven’t taken too broad a class for and thus admitted to it functions not in actuality computable in a number of steps linearly bounded by the lengths of its arguments. 总之，Cobham的这篇文章提出的诸议题：乘法与加法的相对难度，计算的原始步骤，可计算函数的层次等，在深入研究可计算性理论和计算复杂性理论的今天，会继续启发人们，。。。 References A. Cobham, The intrinsic computational difficulty of functions, in Y. Bar-Hillel, ed., Logic, Methodology and Philosophy of Science: Proceedings of the 1964 International Congress, North-Holland Publishing Company, Amsterdam, 1965, pp. 24-30.（ https://www.cs.toronto.edu/~sacook/homepage/cobham_intrinsic.pdf ） The Complexity of Theorem Proving Procedures. Proceedings Third Annual ACM Symposium on Theory of Computing, May 1971, pp 151-158. （ https://www.cs.toronto.edu/~sacook/homepage/1971.pdf ）
The algorithm polynomial time complexity is a big joke ！ Yongjiang Jiang Email: accsys@126.com Any natural number x can be expressed as x = , Where a i is 0 or 1. So that we have x k = . Thus O( x k ) = O(2 nk ), here n is a variable. The polynomial time becomes the exponential time! Is the algorithm polynomial time complexity is not a big joke? 2015-6-6
那天在网上看到一美国佬谈论本人在 arxiv 上发布的那篇论文的博文，觉得很有趣，转贴如下： Note 1 (100422/944am, revised 100422/958am). This note is especially for those who did the 200H project, but may be interesting to everyone. So, the 200H projects critiqued one paper proving P=NP and one paper proving P \neq NP. But it turns out that the supply of resolutions of P versus NP is a rapidly refreshing proof. For example, below is the information on a paper that was posted to arxiv.org a week and a half ago (to see why this is such a surprising claim, please keep in mind that testing whether a graph has a Hamilton (Hamiltonian) cycle is NP-complete, and so if this paper if correct would yield P=NP). One interesting line of the paper is this line (and the italics are not mine---the author italicizes that part of that sentence): This is our big breakthrough (it cost me many years time for getting the algorithm and the proof method ). I just noticed this paper and so for all I know maybe it is right, and if so, the world will transformed (by having thousands of crucial optimization tasks perfectly, exactly solved)... but don't bet on the paper's proof being correct; perhaps that will be a question for next year's CSC200H students to take on. Anyway, the paper can be found at here , and here is the title/abstract: arXiv:1004.3702 (*cross-listing*) Date: Mon, 12 Apr 2010 04:39:27 GMT (76kb) Title: A Polynomial Time Algorithm for Hamilton Cycle and Its Proof Authors: Lizhi Du Categories: cs.DS cs.CC We present a polynomial time algorithm for finding a Hamilton Cycle(Path) in an undirected graph and proves its correctness. A program is developed according to this algorithm and it works very well. This paper declares the algorithm, its proof, and the experiment data. Even only our experiment data is a breakthrough. 下面对这段博文做一简评： 1， 从总的口气上看，他依然持怀疑态度。 2， 论文显然引起了他的强烈兴趣，并且他为此投入了时间和精力（可惜他并非知名权威）。请看这样的句子： but may be interesting to everyone. ， for all I know maybe it is right, 。 3， 到底是美国文化，坦荡直率地发表自己的观点，要是换一种聪明的文化，可能要故作高深地保持沉默，以免万一说错，岂不有损颜面？当然也许还有更聪明的做法。 4， 我英文表达的意思，大致还是可以理解的。 5， 看来，任何人在看到我的论文的第一反应，的总的思维背景，都会是持怀疑态度，因而这样的反应是合理的，我也应适应这样的反应。 6,看来，获得认可的道路可能艰辛而漫长，对此不应太在意。学学老赵的哲学：无所谓。
标签: polynomial
