In the current paper, I present probably the simplest possible abstract formal proof that P ≠ NP, and NP = EXPTIME, in the context of the standard mathematical set theory of computational complexity and deterministic...In the current paper, I present probably the simplest possible abstract formal proof that P ≠ NP, and NP = EXPTIME, in the context of the standard mathematical set theory of computational complexity and deterministic Turing machines. My previous publications about the solution of the P vs. NP with the same result NP = EXPTIME, to be fully correct and understandable need the Lemma 4.1 and its proof of the current paper. The arguments of the current paper in order to prove NP = EXPTME are even simpler than in my previous publications. The strategy to solve the P vs. NP problem in the current paper (and in my previous publications) is by starting with an EXPTIME-complete language (problem) and proving that it has a re-formulation as an NP-class language, thus NP = EXPTIME. The main reason that the scientific community has missed so far such a simple proof, is because of two factors 1) It has been tried extensively but in vain to simplify the solutions of NP-complete problems from exponential time algorithms to polynomial time algorithms (which would be a good strategy only if P = NP) 2) It is believed that the complexity class NP is strictly a subclass to the complexity class EXPTIME (in spite the fact that any known solution to any of the NP-complete problems is not less than exponential). The simplicity of the current solution would have been missed if 2) was to be believed true. So far the majority of the relevant scientific community has considered this famous problem not yet solved. The present results definitely solve the 3rd Clay Millennium Problem about P versus NP in a simple, abstract and transparent way that the general scientific community, but also the experts of the area, can follow, understand and therefore become able to accept.展开更多
It is known that quantum computer is more powerful than classical computer.In this paper we present quantum algorithms for some famous NP problems in graph theory and combination theory,these quantum algorithms are at...It is known that quantum computer is more powerful than classical computer.In this paper we present quantum algorithms for some famous NP problems in graph theory and combination theory,these quantum algorithms are at least quadratically faster than the classical ones.展开更多
As a branch of modern cryptology, sequence cipher technology developed rapidly in recent years. Thispaper applies NP problem to sequence cipher and runs performance analysis for the cipher, and sequence cipher basedon...As a branch of modern cryptology, sequence cipher technology developed rapidly in recent years. Thispaper applies NP problem to sequence cipher and runs performance analysis for the cipher, and sequence cipher basedon NP problem is proved to be an ideal cipher with extreme secrecy.展开更多
In the theory of computational complexity, the travelling salesman problem is a typical one in the NP class. With the aid of a brand-new approach named “maximum-deleting method”, a fast algorithm is constructed for ...In the theory of computational complexity, the travelling salesman problem is a typical one in the NP class. With the aid of a brand-new approach named “maximum-deleting method”, a fast algorithm is constructed for it with a polynomial time of biquadrate, which greatly reduces the computational complexity. Since this problem is also NP-complete, as a corollary, P = NP is proved to be true. It indicates the crack of the well-known open problem named “P versus NP”.展开更多
With a NP hard problem given, we may find a equivalent physical world. The rule of the changing of the physical states is simply the algorithm for solving the original NP hard problem .It is the most natural algorithm...With a NP hard problem given, we may find a equivalent physical world. The rule of the changing of the physical states is simply the algorithm for solving the original NP hard problem .It is the most natural algorithm for solving NP hard problems. In this paper we deal with a famous example , the well known NP hard problem——Circles Packing. It shows that our algorithm is dramatically very efficient. We are inspired that, the concrete physics algorithm will always be very efficient for NP hard problem.展开更多
Many heuristic search methods exhibit a remarkable variability in the time required to solve some particular problem instances. Their cost distributions are often heavy-tailed. It has been demonstrated that, in most c...Many heuristic search methods exhibit a remarkable variability in the time required to solve some particular problem instances. Their cost distributions are often heavy-tailed. It has been demonstrated that, in most cases, rapid restart (RR) method can prominently suppress the heavy-tailed nature of the instances and improve computation efficiency. However, it is usually time-consuming to check whether an algorithm on a specific instance is heavy-tailed or not. Moreover, if the heavy-tailed distribution is confirmed and the RR method is relevant, an optimal RR threshold should be chosen to facilitate the RR mechanism. In this paper, an approximate approach is proposed to quickly check whether an algorithm on a specific instance is heavy-tailed or not. The method is realized by means of calculating the maximal Lyapunov exponent of its generic running trace. Then a statistical formula to estimate the optimal RR threshold is educed. The method is based on common nonparametric estimation, e.g., Kernel estimation. Two heuristic methods are selected to verify our method. The experimental results are consistent with the theoretical consideration perfectly.展开更多
P vs.NP是理论计算机领域最重要的课题之一,而其中的核心是NP完全问题.由于该问题所涉及的概念复杂抽象,对它们的理解存在不少谬误,许多已发表的研究论文都包含着这些谬误.主要是:NP、NP完全概念理解谬误,确定性及非确定性图灵机的概念...P vs.NP是理论计算机领域最重要的课题之一,而其中的核心是NP完全问题.由于该问题所涉及的概念复杂抽象,对它们的理解存在不少谬误,许多已发表的研究论文都包含着这些谬误.主要是:NP、NP完全概念理解谬误,确定性及非确定性图灵机的概念模糊不清,P与NP关系的误读,NP问题研究方向的误导等.本文分析了这些谬误,并揭示了相关概念的实质.通过不同角度多方位分析,对NP完全问题可能的解决途径和研究方向,提供了启发式思路.展开更多
文摘In the current paper, I present probably the simplest possible abstract formal proof that P ≠ NP, and NP = EXPTIME, in the context of the standard mathematical set theory of computational complexity and deterministic Turing machines. My previous publications about the solution of the P vs. NP with the same result NP = EXPTIME, to be fully correct and understandable need the Lemma 4.1 and its proof of the current paper. The arguments of the current paper in order to prove NP = EXPTME are even simpler than in my previous publications. The strategy to solve the P vs. NP problem in the current paper (and in my previous publications) is by starting with an EXPTIME-complete language (problem) and proving that it has a re-formulation as an NP-class language, thus NP = EXPTIME. The main reason that the scientific community has missed so far such a simple proof, is because of two factors 1) It has been tried extensively but in vain to simplify the solutions of NP-complete problems from exponential time algorithms to polynomial time algorithms (which would be a good strategy only if P = NP) 2) It is believed that the complexity class NP is strictly a subclass to the complexity class EXPTIME (in spite the fact that any known solution to any of the NP-complete problems is not less than exponential). The simplicity of the current solution would have been missed if 2) was to be believed true. So far the majority of the relevant scientific community has considered this famous problem not yet solved. The present results definitely solve the 3rd Clay Millennium Problem about P versus NP in a simple, abstract and transparent way that the general scientific community, but also the experts of the area, can follow, understand and therefore become able to accept.
文摘It is known that quantum computer is more powerful than classical computer.In this paper we present quantum algorithms for some famous NP problems in graph theory and combination theory,these quantum algorithms are at least quadratically faster than the classical ones.
文摘As a branch of modern cryptology, sequence cipher technology developed rapidly in recent years. Thispaper applies NP problem to sequence cipher and runs performance analysis for the cipher, and sequence cipher basedon NP problem is proved to be an ideal cipher with extreme secrecy.
文摘In the theory of computational complexity, the travelling salesman problem is a typical one in the NP class. With the aid of a brand-new approach named “maximum-deleting method”, a fast algorithm is constructed for it with a polynomial time of biquadrate, which greatly reduces the computational complexity. Since this problem is also NP-complete, as a corollary, P = NP is proved to be true. It indicates the crack of the well-known open problem named “P versus NP”.
基金86 3National High-Tech Program of China(86 3-30 6 -0 5 -0 3-1) National Natural Science Foundation of China(193310 5 0 ) Chi
文摘With a NP hard problem given, we may find a equivalent physical world. The rule of the changing of the physical states is simply the algorithm for solving the original NP hard problem .It is the most natural algorithm for solving NP hard problems. In this paper we deal with a famous example , the well known NP hard problem——Circles Packing. It shows that our algorithm is dramatically very efficient. We are inspired that, the concrete physics algorithm will always be very efficient for NP hard problem.
文摘Many heuristic search methods exhibit a remarkable variability in the time required to solve some particular problem instances. Their cost distributions are often heavy-tailed. It has been demonstrated that, in most cases, rapid restart (RR) method can prominently suppress the heavy-tailed nature of the instances and improve computation efficiency. However, it is usually time-consuming to check whether an algorithm on a specific instance is heavy-tailed or not. Moreover, if the heavy-tailed distribution is confirmed and the RR method is relevant, an optimal RR threshold should be chosen to facilitate the RR mechanism. In this paper, an approximate approach is proposed to quickly check whether an algorithm on a specific instance is heavy-tailed or not. The method is realized by means of calculating the maximal Lyapunov exponent of its generic running trace. Then a statistical formula to estimate the optimal RR threshold is educed. The method is based on common nonparametric estimation, e.g., Kernel estimation. Two heuristic methods are selected to verify our method. The experimental results are consistent with the theoretical consideration perfectly.
