If the graph isomorphism problem can\'t be solved in polynomial time, do spin-ne
ID: 1321496 • Letter: I
Question
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.
Explanation / Answer
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.