Abstract
Complexity theory as practiced by physicists and computational complexity theory as practiced by computer scientists both characterize how difficult it is to solve complex problems. Here it is shown that the parameters of a specific model can be adjusted so that the problem of finding its global energy minimum is extremely sensitive to small changes in the problem statement. This result has implications not only for studies of the physics of random systems but may also lead to new strategies for resolving the well-known P versus NP question in computational complexity theory.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.