Fragen? Antworten! Siehe auch: Alternativlos
Jetzt gibt es nämlich neue Erkenntnisse über esoterische Geräte, die das in Frage stellen.
MIP is a kind of hypothetical proof system where a regular computer asks questions to a pair of all-knowing but not necessarily honest “oracles” that cannot communicate with one another.
Das klingt ja schonmal absurd, aber für dieses Paper haben sie das Modell nochmal erweitert. Die beiden Orakel sind jetzt quanten-verschränkt, d.h. ihre Antworten sind korreliert. Das hat profunde Auswirkungen, wie sich rausstellt:Last year, Wright and Natarajan drafted a proof showing that the spooky connection in the MIP* class gives the verifier interrogating the entangled provers the power to check even more difficult problems (those whose complexity increases double-exponentially with the size of the input). The added entanglement gives more knowledge to the verifier to ask better questions of the provers (the oracles).
Die aktuelle Arbeit hat jetzt herausgearbeitet, dass dieses Konstrukt noch mächtiger wäre als gedacht.They posit that MIP* could efficiently verify every problem in the “recursively enumerable class,” or RE, basically every problem for which it would take a finite amount of time to calculate if the answer was “yes;” a “no” answer could take an infinite amount of time to calculate. MIP*=RE.
Da fiele dann eben auch das Halteproblem drunter.