Was ist das Informationsvolumen?

Diese Frage wurde Jeannette Wing nach ihrem PCAST-Vortrag über Informatik gestellt.

"Gibt es aus physikalischer Sicht ein maximales Informationsvolumen?"

Jenseits von "Was ist Information?" sollte man auch herausfinden, was "volumen" in diesem zusammenhang bedeutet? Vielleicht ist die maximale Informationsdichte ein besseres Maß.

Lance, es gibt in der Tat einen Satz, der dem Grenzen setzt. Das Margolus-Levitin-Theorem begrenzt die Berechnungsrate in Bezug auf die Energiedichte. Es gibt einen schönen Trick, der gespielt werden kann: Wenn die lokale Energiedichte eine bestimmte Grenze überschreitet, bildet sich ein Schwarzes Loch, das einen Ereignishorizont erzeugt, der Sie im Wesentlichen daran hindert, eine Antwort zu erhalten, indem Sie diesen Raum-Zeit-Bereich kausal von dem trennen Rest des Universums. Seth Lloyd hat eine gute Arbeit, die diesen Trick verwendet, um die Rechenleistung des Universums abzuschätzen ( Phys. Rev. Lett. 88, 237901 (2002) , arXiv ).

Sie können natürlich eine ähnliche Argumentation für jede endliche Region der Raumzeit anwenden.

Dieser Kommentar in ihrem Artikel gibt nicht viel Aufschluss darüber, welche Art von Antwort sie erwartet. Aber sicherlich ist dies inzwischen eine bekannte und ehrwürdige Frage, über die bereits viel bekannt ist. Die Wikipedia-Seite zum holographischen Prinziphat einen guten Überblick. Das Holografischste an diesem Prinzip ist, dass es besagt, dass die Informationskapazität einer Region proportional zu ihrer Oberfläche sein sollte. Wenn Sie an die Informationskapazität denken, wie viele winzige Geräte mit zwei Zuständen Sie dort einbauen können, würden Sie erwarten, dass das Innenvolumen der begrenzende Faktor ist. Diese Intuition gilt bis zu einem gewissen Punkt, aber schließlich wird die Konzentration von Massenenergie, abgesehen von Quantenminiaturisierungsproblemen, so groß, dass sich ein Schwarzes Loch bildet. Grob gesagt ist der Radius im Quadrat (proportional zur Oberfläche) nach Maßanalyse und der Tatsache, dass die Schwerkraft ein inverses Quadratgesetz ist, hier die relevante Größe.

Dies ist eine interessante und etwas amüsante Frage, die jedoch in der aktuellen Form schlecht formuliert ist.

Bei einer Antwort gehe ich ein weiteres Risiko ein und hoffe, dass die Bewertung die ursprüngliche Schwierigkeit und die grundlegende / inhärente "weiche" Mehrdeutigkeit der Frage berücksichtigt und dass es auf der Grundlage des aktuellen Literaturwissens mehrere mögliche Wege gibt, aber möglicherweise keine "richtige Antwort" ".

Die Hauptfrage scheint "Physikalische Analogien in der Informatik" zu sein, zu denen auch das Volumen gehört. Daher ist es in hohem Maße mit dieser anderen Frage verbunden. Physik führt zu TCS?

Um diese Frage zu beantworten, werde ich ein paar verschiedene Ansätze verfolgen, von denen ich denke, dass sie alle verdient haben.

In diesem Fall wird das Volumen streng interpretiert in der Einheit "Raum" oder "Länge gewürfelt". (Obwohl der Begriff "Raum" in der Physik manchmal entweder in Länge oder in Würfellänge gemessen wird.)

$O(n^3)$

$O(n^3)$

$O(n^c)$

Ein anderer Ansatz für eine Volumenanalogie (und andere physikalische Größen) in TCS lautet wie folgt, wie in der anderen Frage erörtert. Es ist bekannt, dass SAT einen Übergangspunkt hat, der dem Übergangspunkt in der Physik / Thermodynamik sehr ähnlich ist, was z. B. bei idealen Gasen unter Kompression von einer Phase zu einer anderen geschieht, z. B. von Gas zu Flüssigkeit. Dies geschieht unter einer Volumenverringerung (etwa des Gasbehälters). In SAT mit zufälligen Eingaben sind die beiden wichtigsten Parameter für die Eingabegröße Klauseln und Variablen. (Ein weiterer Parameter ist die Anzahl der Variablen in Klauseln, obwohl diese für 3-SAT häufig auf 3 festgelegt ist.)

Wenn Sie entweder die Klauseln oder Variablen anpassen, während Sie die andere festhalten, wird die Schwierigkeit des Problems durch den Übergangspunkt "leicht-schwer-leicht" verschoben. Daher scheinen diese Parameter irgendwie analog zu Volume zu sein, obwohl ich die Einzelheiten nicht herausgearbeitet habe. Ein Blick in einige der tiefgründigen Arbeiten zur statistischen Physik von SAT kann das Analogon von Volume aufdecken. Siehe [5] für eine grundlegende Zuordnung von SAT zur Terminologie der statistischen Physik.

[5] Analytische und algorithmische Lösung zufälliger Zufriedenheitsprobleme von Mezard, Parisi, Zechina
http://dynamics.org/Altenberg/UH_ICS/EC_REFS/K-SAT/Mezard.Science.297_812.pdf

$l_p$

$l_p^3$