A PROOF OF THE CONJECTURE THAT THE CLASS P IS A PROPER SUBSET OF THE CLASS NP.doc
《A PROOF OF THE CONJECTURE THAT THE CLASS P IS A PROPER SUBSET OF THE CLASS NP.doc》由会员分享,可在线阅读,更多相关《A PROOF OF THE CONJECTURE THAT THE CLASS P IS A PROPER SUBSET OF THE CLASS NP.doc(13页珍藏版)》请在三一文库上搜索。
1、精品论文http:/A PROOF OF THE CONJECTURE THAT THE CLASS P IS A PROPER SUBSET OF THE CLASS NPWAN-DONG XUAbstract. The planar graph 3-colorability (P3C) is one of NP-complete prob- lem. Duo to probably appearing the second type of mistake in setting colors, a computational algorithm might repeat many times
2、 to decide whether it can correct wrong coloring in many examined subgraphs. Then one can turn P3C by means of analyzing some actual graphs (not with theoretically transformation in polynomial time) into the problem of determining whether there is a planar in innitely many of arbitrary subgraphs. Th
3、e problem of determining whether an arbitrary graph is a planar is in the class P and it can be solved with a polyno- mial time algorithm. But the problem of determining whether there is a planar in12Larbitrary graphs, which have identical order, ofLL k !, or ofk !,=1 k=1 =1 where L = n/3 2 and n is
4、 the order of these graphs, isnt in P, it never besolved with a polynomial time algorithm in the worst case but should be in timeof n2 ( n/3 2)!, and it will cost an innitely length of factorial time when n is a sucient large integer, namely, the time complexity of the problem of P3C isO(n2 ( n/3 )
5、n/3 2 ). So that one decides P3C / P and P NP.Keywords: Problems of P versus NP, 3-colorable, 3-colorability, computability, computational complexity.2000 MSC: 68Q15, 68Q25, 68R10, 03D15, 05C15, 05C38.1. IntroductionSince A. M. Turing presented the concept of computability theory and introduced some
6、 models of computing machines so-called “Turing machine” in 1936 1, the com- puter science has rapidly complemented its important and enormous development. In1946, J. Von Neumann presented a model of “computer with savable program” and leaded some American research institutes to have produced the rs
7、t computing ma- chine with many electron tubes in the world 2. After that time, many of problems computable in principle but intractable in practice have being presented on the table.In 1965, J. Edmonds thought of an idea that an algorithm running in polynomialtime is equivalent to an “eective” algo
8、rithm or a “good” algorithm 3. Then oneAddress: School of Science, Tianjin University, Tianjin, 300072, China.e-mail address: .精品论文has begun to think of another idea that an algorithm running in exponential time is a “bad” algorithm. At latter, one classed the problems solvable with polynomial time
9、algorithm with the class P and the problems solvable with exponential time algo- rithm with the class NP (namely, classed the problems decidable by a deterministic Turing machine in polynomial time with the class P but the problems decidable by an nondeterministic Turing machine in polynomial time w
10、ith the class NP, and one knows that there is P NP but does not know whether there is NP P or not).In 1971, S. A. Cook published his famous paper entitled “The complexity oftheorem-proving procedures” 4. In that paper Cook completed the basis on thetheory of NP-completeness. Since all the problems o
11、f NP-complete can be trans-formed in deliverable and polynomial into another problem which is also a problemof NP-complete, these problems have an equivalent characteristic, namely, if a prob-lem of NP-complete can be solved with polynomial time algorithm, then all otherproblems of NP-complete are a
12、lso solved with polynomial time algorithm, or say, if aproblem of NP-complete cannot be solved with polynomial time algorithm, then allother problems of NP-complete arent also solved with polynomial time algorithm.Cook rst provided that the problem of satisability is a problem of NP-complete,then R.
13、 M. Karp gave 21 of the problems of NP-complete in 1972 5. Up to now,There are more than about 1000 of the problems of NP-complete 6. However, noone knows so far that whether these problems are belong to the class P or not.The current paper devotes to deals with the proof of P NP based on the proble
14、m of deciding whether a planar graph is regularly 3-colorable. In 1973, L. Stockmeyerproved that the problem of planar 3-colorability (P3C) is one of NP-completeness problem (He showed that the necessary and sucient condition of P3C is, theoreti- cally, that a arbitrary graph is 3-colorable with the
15、 key idea of a “vertex substitute” 7, meanwhile, the problem of graph 3-colorability is in the class NP, which could be reduced in polynomial time from the other problem of NP-complete 8-9. Such that, if one can show by means of analyzing an instance (not with a theoretical transforma- tion in polyn
16、omial time from another NP-completeness problem) that it is unsolvable in polynomial time to decide whether a planar graph is regularly 3-colorable or not, then one can conclude that P3C / P and P NP and it will be.According to an actual condition of necessary and sucient to the problem of P3C,which
17、 presented by the author 10, one can easy decide with eyes whether a planargraph is 3-colorable or not, but a computational algorithm cannot assure to solve thisproblem in polynomial time duo to probably appearing the second type of mistake insetting colors.In this paper, one will, in most tradition
18、al and in essence, give a full and particularaccount of this important proposition mentioned above. Some terminologies, symbolsand abbreviations used in the current paper is the same as that used in ref.10.2. The steps to determine whether an arbitrary planar graph is regularly3-colorableThe decidin
19、g whether a arbitrary planar is regularly 3-colorable is very complex. There some steps for this work. These are as follow:(a) Determining whether a plane graph is a connected graph or not, namely, deter- mining (G) = 1 or (G) 1, here (G) is the number of the connected component in G. If there is (G
20、) 1, one should respectively determine whether each of connected components is regularly tc-able.(b) If there is (G) = 1, one should determine whether there are some blocks in Gby denition 6 and 7 and Theorem 4, 5, 6 and 7 in ref.10. If there are blocks BA , BB ,. ., one should individually determin
21、e whether each of blocks is regularly tc-able.(c) For any of block BM in G, here M = A, B, . ., one should determine whatvertices (or how many vertices) are on the periphery cycle of BM . if nM and aMhave been get the next step will be in procedure, where nM is the number of verticesin block BM and
22、aM is the number of vertices on the periphery cycle of BM .(d) one should determine what vertices (or how many cyclic vertices) and whatredial edges (or how many redial edges) in a SGBNNC i correlated to a special inner vertex Vi in BM , and this should be carried out for all bM of cycles correlated
23、 to all inner vertices Vj , Vk , . ., where bM = nM aM , is the number of inner vertices in BM .(e) For every M one should determine whether each of SGBNNCs in BM is regu- larly tc-able by the numbers of cyclic vertices and of redial edges in every SGBNNC by Theorem 2 of ref.10.(f ) Then, for any BM
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- PROOF OF THE CONJECTURE THAT CLASS IS PROPER SUBSET NP
链接地址:https://www.31doc.com/p-3618062.html