Unbounded hardware is equivalent to deterministic Turing machines (Q789180)

Unter Annahme einer physikalisch bedingten unteren Grenze für die Signallaufzeit simulieren die Verf. eine planare physikalische Schaltung durch eine funktionelle deterministische Turing-Maschine und umgekehrt in Polynomzeit. Damit verweisen sie Hoffnungen, durch Einsatz massiver paralleler Hardware NP-schwere Probleme generell in Polynomzeit zu ''knacken'', in das große Reich physikalischer Absurditäten. Die durch Parallelarbeit möglichen Effizienzgewinne sind in dem Modell der Verf. durch ''systolische'' Anordnungen zu erreichen, bei denen ''Schaltungsinseln'' sequentiell vor sich hin arbeiten und nur in großen Zeitabständen sparsam kommunizieren.