I teoretisk informatikk , nærmere bestemt i kompleksitetsteori , er 3-SAT- problemet et problem som hovedsakelig brukes til å demonstrere at andre problemer er NP-harde. Dette er et av Karps 21 NP-komplette problemer .
Dette er begrensningen av SAT-problemet til formler som er konjunktive normale former med maksimalt 3 liter (eller nøyaktig 3 avhengig av kildene). Her er et eksempel på en slik konjunktiv normalform:
Ovenstående formel har 4 ledd, 5 variabler og tre bokstaver per ledd. Det er et spørsmål om å bestemme om man kan tilordne en verdi sann eller usann til hver variabel for å gjøre hele formelen sann.
I 1972 reduserte Richard M. Karp SAT til 3-SAT for å demonstrere at 3-SAT er NP-hard. Dette beviset er til stede i mange arbeider med algoritmer og kompleksitetsteori.
Siden 3-SAT er NP-hard, har 3-SAT blitt brukt for å bevise at andre problemer er NP-harde. Richard M. Karp, i samme artikkel, viser at graffargeproblemet er NP-vanskelig ved å redusere det til 3-SAT på polynomisk tid.
Jan Kratochvil innførte i 1994 en såkalt plan 3-SAT-begrensning som også er NP-vanskelig. Dette er begrensningen av 3-SAT der topartsgrafen sammensatt av variabler og leddsetninger, der en variabel er knyttet til en setning hvis denne paragrafen inneholder denne variabelen, er plan. Dessuten er problemet alltid NP-vanskelig hvis hver ledd inneholder 3 bokstaver og hver variabel vises i maksimalt fire ledd.
ikke-like 3-tilfredshet ( NAE3SAT ) er varianten der vi ber om at de tre variablene i en ledd ikke alle har den samme sannhetsverdien.