Un problema SAT pot ser un problema NP complet?
La qüestió de si un problema SAT (satisfaciabilitat booleana) pot ser un problema NP-complet és fonamental en la teoria de la complexitat computacional. Per abordar-ho, és essencial tenir en compte les definicions i propietats de la NP-completezza i examinar el context històric i teòric que sustenta la classificació de SAT com a problema NP-complet.
Definicions i context
Problema SAT: El problema SAT implica determinar si existeix una assignació de valors de veritat a variables que fa que una fórmula booleana determinada sigui certa. Una fórmula booleana s'expressa normalment en forma conjuntiva normal (CNF), on la fórmula és una conjunció de clàusules i cada clàusula és una disjunció de literals. Per exemple, una fórmula podria semblar:
![\[ (x_1 \lor \neg x_2) \land (\neg x_1 \lor x_3) \land (x_2 \lor \neg x_3). \]](https://eitca.org/wp-content/ql-cache/quicklatex.com-8e405df3b02de2e85a91e7957c82bb5b_l3.png "Presentat per QuickLaTeX.com")
NP (temps polinomial no determinista): Un problema de decisió està en NP si una solució determinada pot ser verificada com a correcta o incorrecta en temps polinomial per una màquina de Turing determinista. Bàsicament, si teniu una solució candidata, podeu comprovar-ne la validesa de manera eficient.
NP-Complet: Un problema és NP-complet si compleix dues condicions:
1. Està en NP.
2. Tot problema de NP es pot reduir a ell en temps polinomial.
El concepte de NP-completezza va ser introduït per Stephen Cook en el seu article seminal de 1971 "The Complexity of Theorem-Proving Procedures", on va demostrar que el problema SAT és el primer problema NP-complet conegut. Aquest resultat es coneix ara com el teorema de Cook.
Teorema de Cook i les seves implicacions
Per entendre per què SAT és NP-complet, hem d'establir dos punts clau:
1. SAT està en NP.
2. Tot problema de NP es pot reduir a SAT en temps polinomial.
SAT és a NP
Per verificar que SAT està en NP, considerem que donada una fórmula booleana i una proposta d'assignació de valors de veritat a les seves variables, podem comprovar si la fórmula s'avalua com a certa en temps polinomial. Això implica avaluar cada clàusula de la fórmula per veure si almenys un literal de cada clàusula és cert. Com que l'avaluació d'una fórmula booleana és un procés senzill que implica un nombre finit d'operacions lògiques, es pot fer de manera eficient. Així, SAT està en NP perquè podem verificar una solució en temps polinomial.
Reducció polinomi-temps
La part més difícil de demostrar que SAT és NP-complet és demostrar que tots els problemes de NP es poden reduir a SAT en temps polinomial. Això implica demostrar que per a qualsevol problema de NP, existeix una funció computable en temps polinomial que transforma les instàncies del problema en instàncies de SAT de manera que el problema original tingui una solució si i només si la instància SAT transformada és satisfactòria.
Per il·lustrar-ho, considereu un problema genèric 
en NP. Per definició, existeix una màquina de Turing en temps polinomial no determinista 
que decideix . La màquina té un procés de verificació en temps polinomial que pot comprovar si un determinat certificat (solució) és vàlid. Podem codificar el funcionament de en una entrada 
com una fórmula booleana tal que la fórmula és satisfacible si i només si accepta .
La codificació inclou els passos següents:
1. Codificació de la configuració: codifica les configuracions (estats, contingut de la cinta i posicions del capçal) de com a variables booleanes. Cada configuració es pot representar mitjançant una seqüència de bits.
2. Codificació de transició: codifica la funció de transició de com un conjunt de restriccions booleanes. Aquestes restriccions asseguren que es capturen transicions vàlides entre configuracions.
3. Estats inicials i d'acceptació: Codifiqueu la configuració inicial (quan s'inicia la màquina) i la configuració d'acceptació (quan la màquina s'atura i accepta) com a restriccions booleanes.
Construint una fórmula booleana que reculli el comportament de , creem una instància de SAT que és satisfacible si i només si hi ha una seqüència de transicions vàlides que condueixen a un estat d'acceptació. Aquesta reducció es pot realitzar en temps polinomial en relació a la mida de l'entrada .
Exemple: Reducció de 3-SAT a SAT
Per dilucidar encara més el concepte de reducció de temps polinomial, considereu el cas específic de reduir 3-SAT a SAT. El problema 3-SAT és un cas especial de SAT on cada clàusula té exactament tres literals. Per reduir 3-SAT a SAT, simplement podem observar que qualsevol instància de 3-SAT ja té la forma requerida per SAT (és a dir, una fórmula CNF). Per tant, la reducció és trivial i es pot fer en temps lineal, que és una reducció en temps polinomial.
Implicacions de que SAT sigui NP-Complet
La classificació de SAT com a NP-complet té implicacions profundes per a la teoria de la complexitat computacional i la resolució de problemes pràctics. Com que SAT és NP-complet, qualsevol problema a NP es pot traduir a una instància SAT. Aquesta universalitat fa que SAT serveixi de referent per a la complexitat d'altres problemes. Si podem trobar un algorisme en temps polinomial per resoldre SAT, podem resoldre tots els problemes NP en temps polinomial, la qual cosa implica 
.
Per contra, si demostrem que no existeix cap algorisme de temps polinomial per a SAT, implicaria que 
. Malgrat les investigacions exhaustives, la qüestió de si segueix sent un dels problemes oberts més significatius de la informàtica.
Aplicacions Pràctiques
A la pràctica, els solucionadors SAT s'utilitzen àmpliament en diversos dominis, com ara la verificació de programari, la intel·ligència artificial i la criptografia. Els solucionadors SAT moderns utilitzen algorismes i heurístiques sofisticades per gestionar instàncies grans i complexes de manera eficient, malgrat la teòrica NP-completezza de SAT. Aquests solucionadors han permès abordar problemes del món real que abans eren insolubles.
Conclusió
El problema SAT és de fet un problema NP-complet, tal com estableix el teorema de Cook. Aquesta classificació es basa en el fet que SAT està en NP i que tots els problemes de NP es poden reduir a SAT en temps polinomial. Les implicacions de que SAT sigui NP-complet són de gran abast, i influeixen tant en la investigació teòrica com en les aplicacions pràctiques en informàtica.
Altres preguntes i respostes recents sobre Complexitat:
- La classe PSPACE no és igual a la classe EXPSPACE?
- La classe de complexitat P és un subconjunt de la classe PSPACE?
- Podem demostrar que les classes Np i P són iguals trobant una solució polinomial eficient per a qualsevol problema NP complet en un TM determinista?
- La classe NP pot ser igual a la classe EXPTIME?
- Hi ha problemes a PSPACE per als quals no es coneix l'algorisme NP?
- Pot un problema estar en classe de complexitat NP si hi ha una màquina de tornejat no determinista que el resolgui en temps polinomial
- NP és la classe de llenguatges que tenen verificadors de temps polinomials
- P i NP són realment la mateixa classe de complexitat?
- És cada llenguatge lliure de context a la classe de complexitat P?
- Hi ha una contradicció entre la definició de NP com a classe de problemes de decisió amb verificadors de temps polinomial i el fet que els problemes de la classe P també tinguin verificadors de temps polinomial?
Veure més preguntes i respostes a Complexity