I problemi decisionali sono uno degli oggetti centrali di studio nella teoria della complessità computazionale. Un problema decisionale è un particolare tipo di problema computazionale la cui risposta è sì o no, oppure alternativamente 1 o 0. Un problema decisionale può essere visto come una lingua formale, in cui i membri della lingua sono istanze la cui produzione è sì, e i non membri sono quelle istanze la cui produzione è no. L' obiettivo è quello di decidere, con l' ausilio di un algoritmo, se una determinata stringa di input sia membro della lingua formale considerata. Se l' algoritmo che decide questo problema restituisce la risposta sì, si dice che l' algoritmo accetta la stringa in ingresso, altrimenti si dice che rifiuta l' ingresso.
Quali sono le due risposte intere a un problema decisionale?
1 o 0 1 o 0 1 o 0