A Probabilistic Attack on NP-complete Problems
–arXiv.org Artificial Intelligence
Using the probability theory-based approach, this paper reveals the equivalence of an arbitrary NP-complete problem to a problem of checking whether a level set of a specifically constructed harmonic cost function (with all diagonal entries of its Hessian matrix equal to zero) intersects with a unit hypercube in many-dimensional Euclidean space. This connection suggests the possibility that methods of continuous mathematics can provide crucial insights into the most intriguing open questions in modern complexity theory.
arXiv.org Artificial Intelligence
Aug-2-2012
- Country:
- North America > United States
- New York (0.05)
- Maryland > Montgomery County
- Rockville (0.04)
- Illinois > Cook County
- Chicago (0.04)
- North America > United States
- Genre:
- Research Report (0.64)
- Technology: