Problemi radi

Introduzione

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

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

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

In un problema rado ciò non avviene, perché il numero di parole di lunghezza $n$, è limitato polinomialmente. In altre parole, il problema $S$ si dice rado, se esiste un polinomio $p$ tale che, per ogni $n$, $S$ ha al più $p(n)$ parole di lunghezza $\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:

$L\subseteq a^{*}$

In questa tipologia di problemi radi si è fortunati, in quanto ci sarà una sola parola di lunghezza 1 ($a$), una sola parola di lunghezza 2 ($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 $S\in A^{*}$ con $S$ rado e $S\not \in P$, allora esiste $T\subseteq a^{*}$ con $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 $\neq$ NP allora ogni problema rado è in NP \ {P $\cup$ NPC}, ossia è un problema NPI;
• se P $\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 $\neq$ NP.

Bibliografia

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