Komplexität #11 - 3SAT in NP

0:00 Plan für die kommenden Videos
3:05 Das Problem 3SAT
7:27 NP-Algorithmus
9:05 Zusatzinfo, Schaefers Theorem

Wir lernen in diesem Video das Problem 3SAT als einen Spezialfall von SAT kennen und überlegen uns kurz, dass es in NP ist. Dies dient als Vorbereitung für das nächste Video, in dem wir NP-Härte von 3SAT und somit NP-Vollständigkeit zeigen wollen.

[peterpeterson]

Kanal aus purem Gold!
Größten Dank dafür

[nilnil]

bro hat mich eigenhändig durch beko gebracht und verdient einen orden

[MrJaleelJamal]

Deine Videos sind echt super und eine tolle Hilfe. In einer Woche schreib ich die Klausur in Berechenbarkeit und Komplexität und deine Videos helfen mir sehr. Vielen Dank dafür. P.S.: Eine Logik-Playlist von dir wäre der Hammer ;)

[anonanon]

wie immer top video. professionell erklärt. man könnte meinen, sie hätten das studiert :)

[zZnighthunterZz]

Danke! Endlich löst sich so einiger Nebel ;)

[sabiplaypuzzles]

Den Satz "3SAT ist nicht nur ein Fernsehsender, sondern auch ein vollständiges Problem" sollte man nie ohne Kontext sagen 😁

[ichbindumm]

Kann ich nicht genau so für 2-KNF argumentieren? Ich habe n Variablen und dementsprechend auch 2^n viele Möglichkeiten diese zu belegen, also ist 2-KNF in NP. Wir wissen aber, dass 2-KNF in P ist, also wo ist denn jetzt der Punkt, an dem ich das behaupten kann?

[dnns]

Mal eine Frage zum Grundsätzlichen Verständnis von 3SAT. Es ist hier und auch auf Wikipedia und wohl überall die Rede von einer 3KNF. Zur KNF hab ich aber eigentlich gelernt, dass diese aus Maxtermen besteht. Habe ich aber 4 Eingabevariablen, dann wären meine Maxterme ja nicht in 3KNF. Gibt es hierfür plötzlich eine andere Definition der KNF?

[cedkhader]

Hi, danke für die gute Arbeit. Ich hätte gern ein Video über die (Circuit Complexity) falls möglich. Danke im Voraus

[isomorphic]

war 3 KNF jetzt, das es nur drei literale gibt oder nicht, weil in ihrem Beispiel gibt es x, y, z, w also vier.