Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Komplexitätstheorie » Gewichtetes 2SAT
Autor
Universität/Hochschule Gewichtetes 2SAT
Schutze
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 23.10.2020
Mitteilungen: 47
  Themenstart: 2021-06-30

Hi, Ich komme bei folgender Aufgabe nicht weiter: Gegeben ist eine gewichtete SAT Instanz in der jede Klausel 2 Literale enthält und ein k Element N. Gefragt: Existiert eine erfüllende Belegung, sodass höchstens k Variablen auf true gesetzt werden? Es soll ein Vorgehen gefunden werden, mit dem eine Instanz in eine äquivalente Instanz umgewandelt wird deren Eingabegröße ausschließlich polynomiell von k abhängt. Es wird also ein FPT-Algorithmus gesucht. Ich habe bislang noch nicht wirklich viele Erfahrungen bezüglich Kernelization und das Vorlesungsmaterial bringt mich aktuell nicht weiter. Durch Recherche bin ich darauf gekommen, dass das Problem wohl auch min ones 2SAT genannt wird, aber mit der Literatur dazu konnte ich leider nicht viel anfangen. Falls jemand hier Tipps oder Anregungen hat, würde ich mich freuen. Viele Grüße


   Profil
Schutze
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 23.10.2020
Mitteilungen: 47
  Beitrag No.1, vom Themenstarter, eingetragen 2021-07-01

Ich poste hier mal einen FPT-Algorithmus, den ich dazu gefunden habe. Leider verstehe ich nicht wie und wieso er funktioniert. https://matheplanet.com/matheplanet/nuke/html/uploads/b/53673_fpt.png


   Profil

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]