Warum werden nicht verteilte Computer- und / oder GPU als nicht deterministische Turing-Maschinen betrachtet, wenn sie mehrere Jobs gleichzeitig ausführen können?

Question

Wir wissen also, dass eine nicht-theoretische Art der Berechnung (NTM) nur ein theoretisches Modell der Berechnung ist.Sie werden in Gedankenversuchen eingesetzt, um die Fähigkeiten und Einschränkungen von Computern zu untersuchen.Wird üblicherweise an DICUSS P vs NP verwendet und wie NP-Probleme bei der Polynomzeit nicht gelöst werden können, es sei denn, die Berechnung wurde auf dem hypothetischen NTM durchgeführt. Wir wissen auch, dass ein NTM eine Reihe von Regeln verwendet, um mehr als eine Aktion vorzuschreiben, die für eine bestimmte Situation durchgeführt werden soll.Mit anderen Worten, versuchen Sie gleichzeitig viele verschiedene Optionen.

Ist das nicht, was verteilte Computing über Commodity-Hardware tut?Führen Sie viele verschiedene mögliche Berechnungen parallel aus?Und die GPU tut dies in einer einzigen Maschine.Warum ist das nicht als NTM angesehen?

Answer 1

In Parallel Computing können die Threads miteinander sprechen und Informationen während der Berechnung austauschen.Im Nondeterminismus ist die einzige "Kommunikation" zwischen Threads, dass wir die oder von allen möglichen Berechnungswegen berechnen.Dies ist viel begrenzter.

Wenn Sie den Nondeterminismus, indem Sie mit parallelen Berechnungen für jede nicht deterministische Wahl auftragen, benötigen Sie eine exponentielle Anzahl von Threads für eine Polynom-Zeit-Berechnung.Wir wissen, wie man in der realen Welt parallele Maschinen baut, wir wissen nicht, wie man nicht deteterministische aufbaut.