| |
| The problem of deciding whether an arbitrary undirected planar graph $G$ is a Hamiltonian (HC) is one of six best important {bf NP}-complete problems. In current paper, by the necessary and sufficient condition of HC, one turned the problem HC into the one of determining whether there does not have any one of forbidden subgraphs in each of spanning subgraphs of $G$. It can be completed in the polynomial time for determining whether there does not have any one of forbidden subgraphs in a spanning subgraph, but it never be completed in the polynomial time for determining whether there exists at least a spanning subgraph in which there never have any forbidden subgraph in infinite many of spanning subgraphs. Such that one can deduced that the time complexity of algorithm for solving the problem HC is $mathcal{O}(n^2 2^{1.5n+Delta})$, here $n$ is the order of $G$ and $Delta$ is $>0$, that is, it is extra exponential of $n$. So one can conclude that HC $NOTIN$ {bf P} and {bf P} $subset$ {bf NP}. |
|
| Keywords:Problems of {bf P} versus {bf NP}, class {bf P}, class {bf NP}, Hamiltonian, Hamiltonian cycle, Hamiltonian graph, computability, computational complexity. |
|
