Site Map Guestbook News Support Download / Purchase Efficiency Testlab About

NP-Complete Problems
Company
Feedback
PCGrates
PCGrate-S(X) Series
PCGrates Screenshots
PCGrates Examples
Our Customers
NP-Complete Problems
Traveling Salesman Problem
Hamiltonian Cycle Problem
NP-Complete Problems Screenshots
NP-Complete Problems Examples
References
I can't find an efficient algorithm, but neither can all these famous people. - Dr. Michael R. Garey and Dr. David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Co., San Francisco, 1979.  
If a problem has an O(nk) time algorithm (where k is a constant), then we class it as having polynomial time complexity and as being efficiently solvable (class P). If there is no known polynomial time algorithm, then the problem is classed as intractable. A problem which can be solved by a series of guessing (non-deterministic) steps but whose solution can be verified as correct in polynomial time is said to lie in class NP. NP-complete problems is set of problems which are all related to each other in the sense that if any one of them can be shown to be in class P, all the others are also in class P.  
 
NP-completeness traditionally pertains to the fields of discrete mathematics and computer science. The theory of intractable problems may be treated as a certain universal mathematical philosophy which is applied by experts in the context of relations between certain classes of algorithms (P = NP or P ≠ NP). In our opinion, over recent years the idea of proving a specified relation between P and NP classes of algorithms has been relegated to the background. At the same time, the major findings in solving NP-complete problems center around the development of approximate polynomial algorithms which make it possible to solve the problems with the accuracy required. Moreover, intensive studies are in progress to evaluate the complexity of particular NP-complete problems and the possibility of using non-exhaustive algorithms (including probabilistic ones) for their solution. Those avenues of investigations and the results gained are of major practical significance on their own, but they are not directly related to the problem P = NP?.  
 
Let us assume the following assertion to be non-contradictory: the complexity level of the problem manifests itself in an early stage of dealing with it. By this we mean that if an algorithm exists which can determine the proper line (or the proper run) for solving the problem at any step in polynomial time, then the problem belongs to class P. If this seems unattainable, the polynomial algorithm for solving the problem is assumed to be nonexistent (or unknown to us). It is worthy to note that the aforementioned reasoning is consistent with the existing view on the problem of NP-completeness, although a diversity of particular NP-complete problems does not make it possible to accurately determine the concept of "a proper run".  
 
For example, when considering existing algorithms for solving the problem "Hamiltonian Cycle" (HCP), there is no way, with the exception of some trivial cases, to specify “the proper run” at the first or at any of the other steps of their work. It would be sufficient if we could determine in polynomial time an edge or several edges possessed (or not possessed) by a Hamilton cycle, if any.  
 
If the graph is specified in a matrix form, it seems generally sufficient for the work of optimization or any calculation algorithms used in solving the problem "Hamiltonian Cycle". No other tentative requirements are imposed upon specifying the graph, and the problem is solved using only one graph (object) prescribed. At the same time, it seems possible to develop an alternative approach to the problem which comprises two steps, namely, (1) to form a certain set of objects brought to some "pre-stress state", and (2) to solve the problem with the use of the selected set of objects. Preliminary data on solutions of the "Hamiltonian Cycle" and "Traveling Salesman" problems (TSP) based on the approach suggested is encouraging, and we hope to publish the new results before long.  
 
At the present time, the question of existence of algorithms which determine "the proper line" for solving NP-complete problems in polynomial time is still an open question. However, this does not preclude a desire for determining those algorithms, if only for some particular cases and for problems with constraints.  
 
Site Map Contacts
Copyright © 1996-2017 International Intellectual Group, Inc.
About Efficiency TestLab Download / Purchase Support News
All rights reserved.