Problemi radi

Introduzione

Un problema ${\displaystyle S}$ può essere inteso come un linguaggio su un certo alfabeto finito ${\displaystyle A}$, ossia ${\displaystyle (L\subseteq A^{*})}$. Se ${\displaystyle L}$ è un linguaggio finito, allora il problema ${\displaystyle S}$ appartiene alla classe P.

In un problema generico, il numero di parole di lunghezza ${\displaystyle n}$ cresce esponenzialmente, poiché:

• ${\displaystyle 2^{1}}$ parole di lunghezza ${\displaystyle 1}$
• ${\displaystyle 2^{2}}$ parole di lunghezza ${\displaystyle 2}$
• ${\displaystyle \ldots }$
• ${\displaystyle 2^{n}}$ parole di lunghezza ${\displaystyle n}$

In un problema rado ciò non avviene, perché il numero di parole di lunghezza ${\displaystyle n}$, è limitato polinomialmente. In altre parole, il problema ${\displaystyle S}$ si dice rado, se esiste un polinomio ${\displaystyle p}$ tale che, per ogni ${\displaystyle n}$, ${\displaystyle S}$ ha al più ${\displaystyle p(n)}$ parole di lunghezza ${\displaystyle \leq n}$.

Conseguenze

I problemi radi sono caratterizzati dal fatto che non possono essere NPC a meno che non sia vero P=NP. Se si dovesse trovare un problema rado che non è polinomiale, allora si riuscirebbe a dimostrare che P non è diverso da NP (ossia si dimostrerebbe che P=NP). Però i problemi radi sono difficili da trattare in quanto occorrerebbe andare a contare, per ogni possibile lunghezza di parola, quante parole ci sono in tale linguaggio.

Esiste però un tipo di problemi radi in cui questo problema non sussiste, e questi problemi sono i problemi 1-ari, ossia problemi definiti su un alfabeto di una sola lettera, come ad esempio:

${\displaystyle L\subseteq a^{*}}$

In questa tipologia di problemi radi si è fortunati, in quanto ci sarà una sola parola di lunghezza 1 (${\displaystyle a}$), una sola parola di lunghezza 2 (${\displaystyle aa}$), e così via. I problemi radi 1-ari sono in grado di rappresentare l'intera stirpe di problemi radi in quanto è verificato che:

se esiste ${\displaystyle S\in A^{*}}$ con ${\displaystyle S}$ rado e ${\displaystyle S\not \in P}$, allora esiste ${\displaystyle T\subseteq a^{*}}$ con ${\displaystyle T\not \in P}$

Quindi i problemi 1-ari sono sfruttabili per tentare di attaccare l'esistenza degli NPI al posto di utilizzare i generici problemi radi. Sfruttando i problemi radi (quindi gli 1-ari) si può dire che:

• se P ${\displaystyle \neq }$ NP allora ogni problema rado è in NP \ {P ${\displaystyle \cup }$ NPC}, ossia è un problema NPI;
• se P ${\displaystyle \neq }$ NP, allora avremmo che ci sarebbe un problema rado in NP se e solo se ce ne fosse qualcuno 1-ario.

Da tutto ciò, si può concludere che esplorare i problemi 1-ari, è una buona strategia per tentare di dimostrare l'esistenza dei problemi NPI e quindi di dimostrare che P ${\displaystyle \neq }$ NP.

Bibliografia

• C. Toffalori, F. Corradini, S. Leonesi, S. Mancini (2005). Teoria della computabilità e della complessità, McGraw-Hill, pagine 166-167