Antworte auf:  Reduktion von SAT auf MAJSAT von LineareAlgebruh
Forum:  Komplexitätstheorie, moderiert von: Bilbo

[Zur Forum-Gliederung] [Wie man Fragen beantwortet] [Themenstart einblenden]

  Alle registrierten Mitglieder können Mitteilungen schreiben.
Benutzername:
Passwort:
Nachricht-Icon:                   
                  
              
Nachricht:


 

Erledigt J


Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
 Show Preview      Write using fedgeo formula editor or Latex.

Smilies for your message:
😃 😄 😁 🙂 🙃 😉 🤗 🤫 🤔 🙄 😴 🤒 😎 😮 😲 😂
🙁 😖 😒 😐 😡 👌 👍 👎 🤢 🤧 🥵 🥶 😵 🤯 😛 😷
Optionen: Deaktiviere HTML in dieser Nachricht
Deaktiviere MATHML in dieser Nachricht. Wenn Dein Text $-Zeichen enthält, die nicht LaTeX-Formeln begrenzen.
Deaktiviere Smilies in dieser Nachricht
Zeige die Signatur (Kann in 'Mein Profil' editiert werden.)
    [Abbrechen]
 
Beachte bitte die [Forumregeln]


Themenübersicht
Fabi
Senior
Dabei seit: 03.03.2002
Mitteilungen: 4572
 Beitrag No.1, eingetragen 2021-01-21 11:39    [Diesen Beitrag zitieren]

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


LineareAlgebruh
Aktiv
Dabei seit: 25.10.2019
Mitteilungen: 98
Wohnort: Bonn

 Themenstart: 2021-01-20 21:10    [Diesen Beitrag zitieren]

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?


 
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]