intrattabilita computazionale

Enciclopedia della Matematica (2013)

intrattabilita computazionale


intrattabilità computazionale caratteristica di un problema per il quale non esiste in generale un algoritmo che assicuri che si giunga alla sua soluzione in un numero finito di passi o comunque in un numero di passi correlato polinomialmente alla dimensione del problema. Presenta caratteristica d’intrattabilità, per esempio, il problema della scomposizione in fattori di un polinomio (→ fattorizzazione).

Tag
Vocabolario
intrattabilità
intrattabilita intrattabilità s. f. [der. di intrattabile]. – Qualità, carattere, condizione di persona o di cosa intrattabile.
computazionale
computazionale agg. [dall’ingl. computational, der. di computation «computazione»]. – Relativo al computare, al calcolo; in partic., linguistica c., altra denominazione, di origine anglo-americana, della linguistica matematica o quantitativa,...