NP-completeness of non-planar Ising model versus polynomial time eigenvalue algorithms From the papers by Barahona and Istrail I understand that a combinatorial approach is followed to prove the NP-completeness of non-planar Ising models. Basic idea is non-planarity here. On the other hand, we have polynomial time algorithms for calculating eigenvalues for matrices. This confuses me. Should not be solving an Ising model be equivalent to calculating the eigenvalue of the Hamiltonian matrix of that model? In that case why is it NP-complete? Is coming up with such a Hamiltonian matrix at the first hand is NP-complete? If it is so, it makes the whole project (coming up with such Hamiltonian and solving it) NP-complete.
 A: Okay, my comments are getting too much, so I will answer.
If I understand your question correctly it says this:


*

*Papers show that the non-planar Ising model (finding its ground state) is NP complete

*On the other hand, finding the eigenvalues of a matrix is polynomial.

*So how do these points reconcile?


The important point here is in the size of the input. If you want to use the matrix diagonalization as a subroutine for your solution to the Ising model, you have to feed it a matrix. The matrix is a square matrix of some size $M \times M$ where $M$ depends exponentially on the number of lattice sites. Suppose we have ising spins that can be either up or down. Then for $N$ lattice sites the Hilbert space has size $M = 2^N$. 
This means that your naive algorithm for solving the Ising model on a lattice with $N$ sites will be polynomial in terms of $M$ but therefore exponential in $N$. 
And what do I mean by a Hamiltonian that's not in matrix form? Well, take the Ising Hamiltonian 
$$H = -\sum_{\langle i,j \rangle} J_{ij} \sigma_i \sigma_j$$
First, since we're talking about Ising spins, the $\sigma$ are not the Pauli matrices! If you used the pauli matrices we'd be dealing with the Heisenberg model. But even then, it wouldn't be in "matrix form". By matrix form, I mean: Pick a basis for the full Hilbert space, then write down a matrix for $H$ in that Hilbert space. This matrix will be exponentially big, as I've explained above.
