Un problema computazionale può essere visto come un' infinita raccolta di istanze insieme ad una soluzione per ogni istanza. La stringa di input per un problema computazionale è indicato come un' istanza di problema, e non deve essere confuso con il problema stesso. Nella teoria della complessità computazionale, un problema si riferisce alla domanda astratta da risolvere. Al contrario, un esempio di questo problema è un' espressione piuttosto concreta, che può servire da spunto per un problema decisionale. Ad esempio, considerare il problema dei test di primalità. L' istanza è un numero (ad esempio 15) e la soluzione è "sì" se il numero è primo e "no" altrimenti (in questo caso "no"). In un altro modo, l' istanza è un particolare input al problema, e la soluzione è l' output corrispondente al dato input. caso problematico.
Qual è il nome dato alla stringa di input di un problema di calcolo?
caso problematico