




















We examine possibility to design an efficient solving algorithm for problems of the class \np. It is introduced a classification of \np problems by the property that a partial solution of size $k$ can be extended into a partial solution of size $k+1$ in polynomial time. It is defined an unique class problems to be worth to search an efficient solving algorithm. The problems, which are outside of this class, are inherently exponential. We show that the Hamiltonian cycle problem is inherently exponential.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。