Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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.

share|cite|improve this answer
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. – mike4ty4 Jun 14 '14 at 10:11

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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