If the graph isomorphism problem can't be solved in polynomial time, do spin-networks in loop quantum gravity violate the Church-Turing thesis? To determine whether or not two graphs are isomorphic (labelled in the case of spin networks, but this doesn't change anything essential) is conjectured to be unsolvable in polynomial time in the worst case scenario. It may or may not be solvable in polynomial time using quantum computers. To compute using spin-networks, we have to determine whether or not two components describe the same network when summing up over quantum states and computing bra-ket norms.


1 Answer 1


The Church-Turing thesis concerns which functions are computable. There are many computable functions with nonpolynomial complexity, so I'm not seeing why you mention polynomial time in the question. For graphs with finitely many vertices and edges, graph isomorphism is definitely computable (just hard).

If your concern is computability, then you should be more worried about whether physics really needs the real numbers, since as far as Church-Turing is concerned, they don't exist.

  • $\begingroup$ But could it be possible that the loop quantum gravity would allow for, if not the construction of a computer going beyond the Turing machine, then for the construction of one which could solve "NP-complete" problems in polynomial time through quantum-gravitational "computation"? Such a machine would obviously be of tremendous import in and of itself, of course. $\endgroup$ Jun 14, 2014 at 10:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.