Visualizza wikitesto di Riduzione in tempo polinomiale

{{F|matematica|febbraio 2020}}

Un [[Linguaggio formale|linguaggio]] A si dice '''riducibile in tempo [[Polinomio|polinomiale]]''' al linguaggio B (denotato con <math>A\le_PB</math>), se esiste una funzione calcolabile f in tempo polinomiale che permetta di convertire istanze del problema di A in istanze di B, tale che <math>w \in A \leftrightarrow f(w) \in B</math>. 

Questa definizione è molto usata nella [[teoria della complessità computazionale]] in quanto se un problema A è riducibile in tempo polinomiale a B allora soluzioni polinomiali di B possono essere usate per risolvere polinomialmente anche A, dato che la composizione di polinomi rimane polinomiale.

Nello specifico con il termine "funzione calcolabile in tempo polinomiale" s'intende una funzione <math>f : \Sigma^* \rightarrow \Sigma^*</math> risolvibile da una [[macchina di Turing]] di tempo polinomiale M arrestandosi con soltanto <math>f(w)</math> sul nastro, dopo aver iniziato con qualsiasi w in input.

{{portale|matematica}}

[[Categoria:Teoria della complessità computazionale]]