| 摘要 |
A system and technique, called Solution Enumeration technique, for finding efficient algorithms for NP-hard combinatorial problems is presented. The solution space of these problems grows exponentially with the problem size. Some examples in this class are: Hamiltonian Circuit, SAT, Graph Isomorphism, and Perfect Matching problems. The core of this technique is a graph theoretical model of an NP-hard problem, viz., counting the perfect matchings in a bipartite graph. This technique is then applied to develop deterministic algorithms using polynomial sequential time or polylogarithmic parallel time (for massively parallel computers) for the search and counting associated with all NP-complete problems. In the past no polynomial time algorithms for these problems were found, and thus are believed to be intractable. This invention thus makes a theoretical as well as practical contribution to the field of computing, and has practical applications in many diverse areas.
|
