Es scheint klar zu sein, dass eine Reihe von Teilbereichen der theoretischen Informatik durch Ergebnisse der theoretischen Physik erheblich beeinflusst wurden. Zwei Beispiele hierfür sind Quantenberechnung Ergebnisse der statistischen Mechanik für Komplexitätsanalysen / heuristische Algorithmen....
Computerkomplexität umfasst die Untersuchung der zeitlichen oder räumlichen Komplexität von Rechenproblemen. Aus der Sicht des Mobile Computing ist Energie eine sehr wertvolle Rechenressource. Gibt es eine gut untersuchte Anpassung von Turing-Maschinen, die den Energieverbrauch bei der Ausführung...
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...
Als TCS-Amateur lese ich populäres, sehr einführendes Material zum Thema Quantencomputing. Hier sind die wenigen grundlegenden Informationen, die ich bisher gelernt habe: Es ist nicht bekannt, dass Quantencomputer NP-vollständige Probleme in der Polynomzeit lösen. "Quantenmagie wird nicht genug...
Viele Experten glauben, dass die Vermutung wahr ist, und verwenden sie für ihre Ergebnisse. Meine Sorge ist, dass die Komplexität stark von der P ≠ N P- Vermutung abhängt .P≠NPP≠NP\mathsf{P} \neq \mathsf{NP}P≠NPP≠NP\mathsf{P} \neq \mathsf{NP} Meine Frage lautet also: Kann / sollte man die...
Ich habe gehört, dass es heuristische Argumente in der statistischen Physik gibt, die Ergebnisse in der Wahrscheinlichkeitstheorie liefern, für die strenge Beweise entweder unbekannt oder sehr schwer zu erhalten sind. Was ist ein einfaches Spielzeugbeispiel für ein solches Phänomen? Es wäre gut,...
Um mein Verständnis zu überprüfen, möchte ich einige Gedanken über den Energiebedarf der Berechnung teilen. Dies ist eine Folge meiner vorherigen Frage und könnte mit Vinays Frage nach den Erhaltungsgesetzen zusammenhängen . Es ist mir aufgefallen, dass aus thermodynamischer Sicht das Ausführen...
Diese Frage ist eine Fortsetzung der Frage zu DNA-Algorithmen, die Aadita Mehra gestellt hat . In Kommentaren sagte Joe Fitzsimmons zum Teil: Der Radius des Systems muss proportional zur Masse skaliert werden, um dies zu vermeiden. Die Rechenleistung skaliert höchstens linear in der Masse. Ihre...
Stellen Sie sich ein elektrisches Netzwerk vor, das als ebener Graph G modelliert ist, wobei jede Kante einen 1Ω-Widerstand darstellt. Wie schnell können wir den genauen effektiven Widerstand zwischen zwei Eckpunkten in G berechnen ? Wie schnell können wir den exakten Strom berechnen, der entlang...
Diese Frage wurde von Physics Stack Exchange migriert, da sie über Theoretical Computer Science Stack Exchange beantwortet werden kann. Vor 6 Jahren migriert . Bei der adiabatischen Quantenberechnung (AQC) wird die Lösung eines Optimierungsproblems im Grundzustand eines [problem] Hamiltonian . Um...
Reversible Computing ist ein Rechenmodell, das nur thermodynamisch reversible Operationen zulässt. Nach dem Landauer-Prinzip, das besagt, dass das Löschen einer Information Joule Wärme freigesetzt werden, werden Übergangsfunktionen ausgeschlossen, die nicht eins zu eins sind (z. B. die Booleschen...
Ist es möglich, algorithmisch zu testen, ob eine berechenbare Zahl rational oder ganzzahlig ist? Mit anderen Worten, könnte eine Bibliothek, die berechenbare Zahlen implementiert, die Funktionen bereitstellen, isIntegeroder isRational? Ich vermute, dass es nicht möglich ist und dass dies irgendwie...
Eines der erstaunlichen Dinge in der Informatik ist, dass die physikalische Implementierung in gewisser Weise "irrelevant" ist. Die Menschen haben erfolgreich Computer aus mehreren unterschiedlichen Substraten gebaut - Relais, Vakuumröhren, diskrete Transistoren usw. Die Menschen könnten bald...
Es gibt Forscher, die zeigen, dass das Löschen von Bits Energie verbrauchen muss. Gibt es jetzt Forschungen zum durchschnittlichen Energieverbrauch von Algorithmen mit der Rechenkomplexität ? Ich vermute, die Komplexität von hängt mit dem durchschnittlichen Energieverbrauch zusammen. Ich hoffe, ich...
Ich habe veröffentlichte Bücher, Artikel und Artikel über Quantum-Computing gelesen. Ich fand heraus, dass alle Materialien, die ich gesehen habe, anstatt das Quantentor von der Grundphysik bis zur Abstraktion zu beschreiben, sich bemühen , nicht über die Implementierungsdetails von Quantentoren zu...
Ich suche nach Beispielen für schwierige Probleme (in NP oder schwieriger) aus der Informatik, die auf Modelle physikalischer Prozesse reduziert werden können. Zum Beispiel kann max-2-sat in einem Ising-Modell auf Energieminimierung reduziert werden. Ich würde gerne weitere Beispiele für diese Art...
Hintergrund Die Schaltungskomplexität ist definiert als der Satz von Schaltungsfamilien (dh Folgen von Schaltungen, eine für jede Eingangsgröße) mit begrenzter Tiefe und Polynomgröße, die unter Verwendung von unbegrenztem Fan-In AND, OR und NOT erstellt wurden.AC0AC0AC^0 Die Paritätsfunktion mit...
Meine Frage betrifft Quantenalgorithmen für QED-Berechnungen (Quantenelektrodynamik) in Bezug auf die Feinstrukturkonstanten. Solche Berechnungen (wie mir erklärt) Taylor-ähnliche Reihen wobei die Feinstrukturkonstante (um 1/137) ist und der Beitrag von Feynman-Diagrammen mit Schleifen ist. α c k...
Bekannte Beispiele für Berechnungen, die von Naturphänomenen inspiriert sind, sind Quantencomputer und DNA-Computer. Was ist über das Potenzial und / oder die Einschränkungen des Rechnens mit Maxwells Gesetzen oder der Schwerkraft bekannt? Das heißt, die "schnellen" Lösungen der Natur für Maxwells...
Angesichts des heutigen Todes von Stephen Hawking habe ich mich gefragt, ob eines seiner Ergebnisse einen direkten Einfluss auf cs hat. Der offensichtliche Kandidat wäre das Quantencomputing oder vielmehr der Aufbau eines physischen Quantencomputers, aber vielleicht gibt es Ergebnisse, die andere...