complessita computazionale P

Enciclopedia della Matematica (2013)

complessita computazionale P


complessità computazionale P locuzione con cui si indica la complessità di calcolo di un problema di decisione (un problema cioè la cui soluzione può essere soltanto «sì» oppure «no») risolubile in un tempo polinomiale (correlato alla dimensione del problema). In sostanza per un problema di complessità computazionale P esiste un algoritmo di soluzione il cui tempo di risoluzione è funzione polinomiale delle dimensioni dei valori in input (→ complessità computazionale).

Tag
Vocabolario
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,...
complessità
complessita complessità s. f. [der. di complesso1]. – 1. L’esser complesso (nelle varie accezioni dei sign. 1 e 2 di quest’agg.): c. di una questione, di un ragionamento, di una costruzione teorica; c. di un atto giuridico; esaminare una...