Forum:  Komplexitätstheorie
Thema: Reduktion von SAT auf MAJSAT
Themen-Übersicht
LineareAlgebruh
Aktiv
Dabei seit: 25.10.2019
Mitteilungen: 108
Wohnort: Bonn
Themenstart: 2021-01-20 21:10
Guten Abend. Ich versuche derzeitig diese Aufgabe zu lösen: https://www.matheplanet.com/matheplanet/nuke/html/uploads/b/52110_Unbenannt.png 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?

Fabi
Senior
Dabei seit: 03.03.2002
Mitteilungen: 4575
Beitrag No.1, eingetragen 2021-01-21 11:39
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



Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=251863=510003
Druckdatum: 2021-12-02 07:13