Kann Blitz verwendet werden, um NP-vollständige Probleme zu lösen?

Ich bin ein MS / BS-Informatiker, der sich fragt, warum Blitze nicht verwendet werden können (oder können?), Um NP-Probleme effizient zu lösen, aber ich verstehe die Physik hinter Blitzen nicht, also poste ich hier .

Was mir an Blitzen eigenartig erscheint, ist, dass sie dem "einfachsten" Weg zu einem bestimmten Ziel zu folgen scheinen, im Gegensatz zu nur dem kürzesten Weg. Dies scheint analog (identisch?) zu den Gewichten im Problem des Handlungsreisenden zu sein.

Da der Blitzprozess die Luft ionisiert und sich schnell den einfachsten Weg zu suchen scheint, habe ich 2 Fragen:

1) Verwendet Lightning eine ähnliche Methode wie Dijkstras Ansatz (so dass ein "gut genug" Pfad in polynomieller Zeit gefunden wird, aber nicht unbedingt die "beste aller Optionen")? Ist es im Grunde ein NP-"Löser"?

Wenn die Antwort auf die obige Frage "nein" ist und es tatsächlich die beste Wahl ist:

2) Könnte der Auswahlprozess des Blitzes in einem Computeralgorithmus verwendet werden, um ein Problem vom Typ Handlungsreisender in polynomieller Zeit zu lösen, und

3) Wenn nicht, könnte eine willkürliche Reihe von gewichteten Knoten irgendwo physisch eingerichtet werden und Strom durch sie fließen lassen und die Ergebnisse jedes Mal, wenn ein Benutzer einen kürzesten Weg wissen möchte, in eine Art Computermechanismus zurückgeführt werden?

Wenn Sie diesen Ansatz verwenden könnten, um NP-schwere Probleme schnell zu lösen, würden Sie Ihren Namen in den Nachrichten und vielleicht in den Geschichtsbüchern finden. Warum hat also niemand Blitze eingesetzt, um dieses Problem zu lösen?

UPDATE: Ein weiterer Aspekt, den ich interessant finde: Wenn ein Blitz einschlägt, ionisiert er die Luft, um den kürzesten Weg zu finden. Wenn die Welt völlig flach wäre (und die Wolken auch), würde dies die gesamte Luft gleichermaßen ionisieren. Was mich zu der Annahme verleitet, dass die vom Blitz "ausgewählte" Route alle Punkte enthält, was eine Voraussetzung zu sein scheint, um die beste aller Lösungen zu finden.

Wussten Sie, dass NP nicht für nicht-polynomial steht?
Zephyr: Etwas gelernt. Vielen Dank! Ich frage mich immer noch, ob der Blitz ein schwieriges NP-Problem in P-Zeit löst.
Die nichtdeterministische Maschine löst viele NP-schwere Probleme „in P-Zeit“. ;)
1 -> nein und ja. Sie brauchen einen anderen Prozess, um die schlechten Täler zu verlassen. Aber die Tests können multipliziert werden, nicht um die Verteilungswahrscheinlichkeiten zu finden, sondern um effektiv das beste Ergebnis auszuwählen, wenn es nicht zu selten ist. Eine andere Form des Glühens

Antworten (1)

1) Ja, es wird grundsätzlich eine nicht optimale Lösung gefunden. An jedem Punkt sucht die Spitze des Strahls nach dem größeren Potentialgradienten, die Ladung im umgebenden Volumen wächst und polarisiert das umgebende Material (in diesem Fall Luft), bis ein größerer Gradient auftritt und der Strahl in dieser Richtung weitergeht. Deshalb sieht der Lichtweg wie ein Puzzle aus; Es ist im Grunde eine Monte-Carlo-Suche.

Um nicht zu sagen, dass Sie dies nicht anwenden können, um effiziente Lösungen des Traveller-Problems zu finden. Dies würde eine programmierbare Konfiguration mit kapazitätsbezogenen Gewichten erfordern, damit der Lichtbogen den besten Weg findet, der auch Ihr spezielles Adjazenzmatrixproblem löst. Dies würde wahrscheinlich nur durch die Tatsache behindert, dass sich der Lichtbogen zum Durchqueren über die Kapazitätsbarriere brennen muss, es sei denn, Sie finden ein billiges, austauschbares Material, das auch konfigurierbar sein kann (das Gewicht muss sich anpassen). die Gewichte der Adjazenzmatrix) ist es billiger, diese Berechnung in einem Standardcomputer durchzuführen.

+1. Es sollte betont werden, dass die Lösung nicht optimal ist . Die Form, die Blitze annehmen, sieht im Allgemeinen fraktal aus und verzweigt sich tatsächlich auch in mehrere kleinere Pfade, die an keiner sinnvollen Stelle enden. Es ist ziemlich klar, dass die vom Blitz gefundene "Lösung" nicht nur kein globales Optimum ist, sondern nicht einmal offensichtlich ein lokales Optimum, es sei denn, Sie möchten unkontrollierbare und nicht gemessene Effekte von atmosphärischen Schwankungen von einem Kilometer oder mehr berücksichtigen B. der Ionisation usw. Es ist sicherlich nicht ersichtlich, dass schwierige Fälle von NP-vollständigen Problemen gelöst werden.
Ebenso gab es vor einigen Jahren Aufsehen über Blasen zwischen Platten mit einigen Stiften durch sie, die das Steiner-Baum-Problem "lösten" (die Lösung sind die Linien, die durch Blasengrenzflächen gebildet werden) - in diesem Fall ist es offensichtlicher als ein lokales Minimum gefunden wird, aber Sie können das Experiment einige Male durchführen, um zu sehen, dass es globale Minima nicht zuverlässig findet.
Tatsächlich hat Scott Aaronson sogar ein Experiment mit Seifenblasen durchgeführt, um das Gegenteil zu beweisen! Er hat auch eine sehr schöne Umfrage geschrieben: arxiv.org/abs/quant-ph/0502072
+1. Aber manchmal vergrößern die physikalischen Experimente Konvergenzkurven und können helfen, die Algorithmen zu verfeinern
Kann Blitz verwendet werden, um NP-vollständige Probleme zu lösen?
AntwortenHierDatenschutz-Bestimmungen1y, 0v