Problema de decisió

En teoria de la computabilitat i en complexitat computacional, un problema de decisió és una qüestió en algun sistema formal amb una resposta sí o no. Problemes amb respostes més complexes es coneixen com problemes funcionals.

Per exemple, es pot tenir un problema de decisió «donats dos nombres x i y, x és divisor enter de y?». Aquesta és una pregunta de resposta sí o no, i la seva resposta depèn dels valors de x i de y. Un algorisme per aquest problema de decisió hauria de contestar com, donats x i y, es pot determinar si x és divisor enter de y.

Els problemes de decisió acostumen a ser menys útils intuïtivament parlant que no pas els problemes funcionals, que poden tenir qualsevol resposta, no només si o no. Per exemple, un problema funcional pot ser "donats dos nombres x i y, quan es x dividit per y?". Tot i això, per a la teoria de complexitat computacional, és més senzill d'estudiar els problemes de decisió. A la teoria de la computabilitat, intenta classificar els problemes de decisió basant-se en com de «difícils» són, en termes de requeriments computacionals que es necessiten per l'algorisme més eficient per aquest problema de decisió.

Definició

Un problema de decisió és qualsevol pregunta de sí o no sobre un conjunt infinit d'entrades. Per això, és tradicional definir el problema de decisió en termes del conjunt d'entrades pel qual el problema retorna un sí. En aquest sentit, un problema de decisió és equivalent a un llenguatge formal.

Formalment, un problema de decisió és un conjunt comptable S i una funció

$f:S\to \lbrace 0,1\rbrace .$

Sigui A la inversa de f per 1:

$A:=\lbrace s\in S|f(s)=1\rbrace =f^{-1}(\lbrace 1\rbrace ).$

El problema és anomenat decidible si A és un conjunt recursiu. S'anomena parcialment decidible si A és conjunt recursivament enumerable. D'altre manera, el problema s'anomena indecidible.

Es pot donar una altre definició alternativa en termes de funcions computables:

Si f és una funció computable total, el problema s'anomena computable. Si f només és una funció parcial, el problema s'anomena parcialment computable. D'altre manera el problema és incomputable.

Notes

Cal fer notar que un problema de decisió sempre és un conjunt de problemes relacionats que d'alguna forma és prou gran. Un sol problema P és sempre trivialment decidible assignant-li la funció constant f(P)≡0 o f(P)≡1.

La majoria de problemes es pot reformular com un problema de decisió mitjançant reduccions, sovint amb molt poc efecte en la quantitat de temps o espai que es necessita per resoldre el problema. La majoria dels problemes més complexos s'han reformulat com a problemes de decisió perquè es fan més senzill d'estudiar i resoldre, i provar també que aquests problemes són prou difícils per mostrar que altres problemes més complexos són igual de complexos.

Exemples

Problemes de decisió importants inclouen el problema de la parada; per més informació, vegeu la llista de problemes indecidibles. En complexitat computacional, els problemes de decisió que són complets són usats per caracteritzar les classes de complexitat dels problemes de decisió. Exemples importants són el problema de satisfacibilitat booleana i les seves variants, així com l'undirected i el directed reachability problem.

Història

El Entscheidungsproblem, paraula alemanya per «problema de decisió», és atribuït a David Hilbert: «A la conferència del 1928, Hilbert va fer aquestes reflexions. Primer, les matemàtiques foren completes... En segon lloc, les matemàtiques foren consistents... I en tercer lloc.. són les matemàtiques decidibles? Amb això es referia a si existeix un mètode definitiu que pugui, en principi aplicat a qualsevol afirmació, i que garanteixi que produirà una decisió correcta sobre si l'afirmació és certa» (Hodges, p. 91). Hilbert creia que «a les matemàtiques no hi ha ignorabimus» (Hodges, p. 91ff) volent dir que 'no sabem i no sabrem'. Vegeu David Hilbert i Problema de la parada per més informació.

Equivalència a problemes computacionals

Cada problema de decisió és reductible a un problema de computació, ja que cada classe de problema sí o no és reductible a un predicat de la forma "És $P(x_{1},...,x_{n})$ veritat?". Per exemple, l'exemple anterior es pot reduir a "És $P(x,y)$ veritat?". Aquesta forma predicativa és reductible a la funció indicadora

$f(x_{1},...,x_{n})=\left\{{\begin{matrix}1,&{\mbox{si }}P(x_{1},...,x_{n}){\mbox{ es cert}}\\0,&{\mbox{si }}P(x_{1},...,x_{n}){\mbox{ es fals}}\end{matrix}}\right\}$

per tant, decidir qualsevol $P(x_{1},...,x_{n})$ és veritat és equivalent a computar el valor de $f(x_{1},...,x_{n}).$.

Referències

• Andrew Hodges, Alan Turing: The Enigma, Simon i Schuster, New York. Cf Chapter "The Spirit of Truth" per una mica d'història fins al treball de Turing. Una bona biografia.

Hodges referencia una biografia de David Hilbert: Constance Reid, Hilbert (George Allen & Unwin; Springer-Verlag, 1970). Aparentment hi ha edicions més recents.