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?