Die Mathe-Redaktion [Home] - Neues auf einen Blick 28.02.2021 16:56 [Neues] [Forum] [Suche] - Registrieren/Login
 
Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Komplexitätstheorie » Reduktion von SAT auf MAJSAT		Druckversion
Druckversion
Autor
Universität/Hochschule J Reduktion von SAT auf MAJSAT
LineareAlgebruh
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 25.10.2019
Mitteilungen: 94
Herkunft: Bonn
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2021-01-20


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?

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Fabi
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.03.2002
Mitteilungen: 4551
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.

Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
LineareAlgebruh hat die Antworten auf ihre/seine Frage gesehen.
LineareAlgebruh hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
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]