Riduzione in tempo polinomiale

Questa voce o sezione sull'argomento matematica non cita le fonti necessarie o quelle presenti sono insufficienti.

Un linguaggio A si dice riducibile in tempo polinomiale al linguaggio B (denotato con ${\displaystyle A\leq _{P}B}$), se esiste una funzione calcolabile f in tempo polinomiale che permetta di convertire istanze del problema di A in istanze di B, tale che ${\displaystyle w\in A\leftrightarrow f(w)\in B}$.

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 ${\displaystyle f:\Sigma ^{*}\rightarrow \Sigma ^{*}}$ risolvibile da una macchina di Turing di tempo polinomiale M arrestandosi con soltanto ${\displaystyle f(w)}$ sul nastro, dopo aver iniziato con qualsiasi w in input.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica