Home > Papers

 
 
A proof of the conjecture that the class P is a proper subset of the class NP
Xu Wandong *
School of Science, Tianjin University
*Correspondence author
#Submitted by
Subject:
Funding: none
Opened online:15 November 2007
Accepted by: none
Citation: Xu Wandong .A proof of the conjecture that the class P is a proper subset of the class NP[OL]. [15 November 2007] http://en.paper.edu.cn/en_releasepaper/content/16366
 
 
The planar graph 3-colorability (P3C) is one of {bf NP}-complete problem. Duo to probably appearing the second type of mistake in setting colors, a computational algorithm might repeat many times 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 infinitely many of arbitrary subgraphs. The problem of determining whether an arbitrary graph is a planar is in the class {bf P} and it can be solved with a polynomial time algorithm. But the problem of determining whether there is a planar in arbitrary subgraphs, which have identical order, of $sumlimits_{nu=1}^{L}dbinom{L}{nu}nu!$, or of $sumlimits_{k=1}^{L}sum limits_{nu=1}^{k}dbinom{k}{nu}nu!$, where $L=lceil n/3 rceil-2$ and $n$ is the order of these graphs, isn\
Keywords:Problems of {bf P} versus {bf NP}, 3-colorable, 3-colorability, computability, computational complexity.
 
 
 

For this paper

  • PDF (0B)
  • ● Revision 0   
  • ● Print this paper
  • ● Recommend this paper to a friend
  • ● Add to my favorite list

    Saved Papers

    Please enter a name for this paper to be shown in your personalized Saved Papers list

Tags

Add yours

Related Papers

Statistics

PDF Downloaded 397
Bookmarked 0
Recommend 5
Comments Array
Submit your papers