Hier ist das Problem:
Wir haben ein Quadrat mit Zahlen von 1..N in einigen Zellen. Es ist erforderlich, um festzustellen, ob es zu einem magischen Quadrat vervollständigt werden kann.
Beispiele:
2 _ 6 2 7 6
_ 5 1 >>> 9 5 1
4 3 _ 4 3 8
7 _ _
9 _ _ >>> NO SOLUTION
8 _ _
Ist dieses Problem NP-vollständig? Wenn ja, wie kann ich das beweisen?
cc.complexity-theory
np-hardness
np
puzzles
levanovd
quelle
quelle
Antworten:
Das Ausfüllen eines teilweise ausgefüllten lateinischen Quadrats ist NP-Complete. "Die Komplexität der Vervollständigung von lateinischen Teilquadraten" Charles J. Colbourn. Discrete Applied Mathematics, Band 8, Ausgabe 1, April 1984, Seiten 25-30 http://dx.doi.org/10.1016/0166-218X(84)90075-1
Kann ein lateinisches Quadratproblem durch modulare Arithmetik in ein magisches Quadratproblem umgewandelt werden? Meine Intuition sagt ja, aber der Rest meines Gehirns sagt "Mach dich wieder an die Bewertung!"
quelle
Diese Frage besteht aus zwei Teilen: Erstens ist das Problem in NP und zweitens ist es NP-schwer?
Für den ersten Teil habe ich eine positive Antwort mit einem nicht offensichtlichen Beweis. (Vielen Dank an Suresh für den Hinweis auf einen früheren Fehler.)
Betrachten Sie den folgenden Weg, um die Frage als Entscheidungsproblem zu formalisieren:
Wenn wir die Einschränkung hinzufügen, dass jede der ganzen Zahlen genau einmal im magischen Quadrat vorkommen muss, dann liegt das resultierende Entscheidungsproblem für MAGIC SQUARE COMPLETION offensichtlich in NP. Die Definition eines magischen Quadrats in der Encyclopædia Britannica von 1911 nach Euler unterliegt dieser Einschränkung. Der Wikipedia-Artikel verwendet dagegen derzeit die Terminologie "normales magisches Quadrat" und reserviert "magisches Quadrat" für die uneingeschränkte Version.1,2,…,n2
Mit einer von n Gittern, mindestens n Zahlen muss angegeben werden, da sonst die Antwort triviale „JA“ für die uneingeschränkte Version. Es kann daher angenommen werden, dass die Größe des Eingangs in diesem Fall mehr als n Bits erfordert . Für die normale Version ist es möglich, dass es Eingaben gibt, die wenige Bits erfordern, aber keine Lösung haben. Um solche Komplikationen zu vermeiden, habe ich angegeben, dass n unär ist.n n n n n
Das Argument verwendet eine Grenze für die mögliche Größe von Ganzzahlen, die in Lösungen angezeigt werden. Im Normalfall ist diese Schranke offensichtlich , aber im allgemeinen Fall ist es nicht a priori offensichtlich, dass eine solche Schranke existiert. Es stellt sich heraus, dass eine Exponentialgrenze existiert.n2
Dies erschien auch als Satz 4.7 in:
Dies ergibt folgendes:
Anhand von Papadimitrious Lösungsbindung für eine Instanz von INTEGER LINEAR PROGRAMMING kann auch gezeigt werden, dass die Version, in der die Zahlen alle nicht negativ sein müssen, ebenfalls in NP ist.
quelle