[Solved]: Why does the NP completeness of the Hartree-Fock method not lead to difficulty in practical calculation?

Problem Detail: 

I read Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory. In appendix, it is claimed that

In the following, we show that approximating the ground state energy using the Hartree-Fock method is an NP-complete problem

As far as I know, if a problem being NP-hard, it is unlikely to be solved within polynomial time. If Hartree-Fock is NP-complete, computation for large system is unlikely to be possible. However, experience seems to suggest that Hartree-Fock could always be done within polynomial time. There are vast applications of Hartree-Fock method on various many-electron system: atoms, molecules, and solids. The claim from the arxiv paper is rather in contraction with my experience

My question is, why the Hartree-Fock method is applicable to wide class of many-electron system while it is NP-complete? Is that because its average complexity is low or any other reason?

Asked By : user26143

Answered By : D.W.

There is plenty of precedent for problems that are NP-hard (in worst-case complexity) but can often be done in practice on many instances that arise in practice (e.g., because their average-case complexity is low, or for other reasons).

NP-hardness relates to the worst-case complexity of a problem. However, worst-case hardness isn't always representative of typical-case hardness. Sometimes typical instances are much easier than the worst-case instances. Therefore, NP-hardness results aren't always an indication that the problem can't be solved acceptably well in practice.

As Yuval Filmus explained so well in a comment:

I'm not sure there is any better answer than the fact that the algorithms work on real-world instances. NP-hardness is a worst-case concept, and sometimes the worst case is simply irrelevant. It is a challenging problem to characterize which properties of real-world instances render the problem solvable. Smooth analysis is one answer, and there might be others in the non-rigorous literature.

I recommend you take a look at Dealing with intractability: NP-complete problems for an overview of common methods for dealing with NP-hardness: i.e., for figuring out ways to solve a problem good enough for practical purposes, when we know it is NP-hard.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/27905

3.2K people like this

 Download Related Notes/Documents