Informally, two entangled gods who can’t communicate classically could convince you whether any given TM halts or not; but only because you are assuming that they can’t communicate classically. How do you become convinced that they can’t communicate classically? Unless you are doing the thing in one step, sending two superbly organized queries off in opposite directions in such a way that the answers come back soon enough that you can be sure there was no communication because you are already sure of how far away each of the gods really is from you and from the other one and know they haven’t moved closer to you in the meantime, I don’t see how you could know they weren’t communicating classically. Does the protocol account for this?

]]>Rather the split property implies the two separate properties: Operational Independence and Commensurability. Together these ensure that despite the ubiquitous entanglement present in QFT two separate regions are operationally local. Operational Independence means the states preparable for one region and the operations that can be performed there are not dependent on the second region. Commensurability is just the usual commutativity for spacelike regions, i.e. choice of observable in region A doesn’t disturb statistics in region B.

]]>In addition, though, if you have an oracle for telling you whether an NP-complete problem instance is satisfiable or not, a standard exercise shows that you can also use that oracle to *find* satisfying assignments in polynomial time, whenever they exist. (Hint: use binary search.)

just to make sure I’m not losing my mind here…

When it comes to NP hard problems, we do not know of any efficient way to find out whether a solution (or more than one) exists vs there are no solution at all, right?

So the method would say “no solution exists” or “at least one solution exists”, but without giving back any actual solution.

]]>