|
Autor |
Reduktion von SAT auf MAJSAT |
|
LineareAlgebruh
Aktiv  Dabei seit: 25.10.2019 Mitteilungen: 94
Herkunft: Bonn
 |
Guten Abend.
Ich versuche derzeitig diese Aufgabe zu lösen:
Zunächst erschien es mir sehr logisch, dass dieses Problem nicht in P liegen kann, da mir nur einfiele, alle 2^n Kombinationen durchzugehen und unter diesen 2^(n-1) + 1 erfüllende Kombinationen zu finden, das ist nicht polynomiell, und ich wüsste nicht, wie man besser suchen könnte. Ich hab auch mal online ein wenig nachgeschaut und herausgefunden, dass dieses Problem allgemein unter dem Namen MAJSAT bekannt ist. Dieses Problem liegt sogar nicht mal mehr in NP. Nun würde ich gerne zeigen, dass es NP-schwer ist. Dazu muss man "einfach" irgendein NP-schweres Problem auf MAJSAT poly. reduzieren, in der Vorlesung sah das auch immer so einfach aus, aber hier habe ich leider nicht mal einen Ansatz, was man versuchen könnte. Hat da jemand vielleicht einen kleinen Tipp?
|
Notiz Profil
Quote
Link |
Fabi
Senior  Dabei seit: 03.03.2002 Mitteilungen: 4560
 |     Beitrag No.1, eingetragen 2021-01-21
|
Hi,
Tipp: Fällt dir eine (möglichst einfache!) logische Formel ein, die in genau der Hälfte der Fälle wahr ist? Wie könnte man damit eine Instanz von SAT so manipulieren, dass diese auch in mindestens der Hälfte der Fälle wahr ist?
vG,
Fabi
----------------- "There would be the mathematical equivalent of worldwide rioting." (P.C.)
Willst du Hamburg oben sehen, musst du die Tabelle drehen.
|
Notiz Profil
Quote
Link |
LineareAlgebruh hat die Antworten auf ihre/seine Frage gesehen. LineareAlgebruh hat selbst das Ok-Häkchen gesetzt. | [Neues Thema] [Druckversion] |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen. Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|