Problemi radi

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

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

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

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

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 ⊆ a ∗ {\displaystyle L\subseteq a^{*}}

In questa tipologia di problemi radi si è fortunati, in quanto ci sarà una sola parola di lunghezza 1 ( a {\displaystyle a} ), una sola parola di lunghezza 2 ( a a {\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 S ∈ A ∗ {\displaystyle S\in A^{*}} con S {\displaystyle S} rado e S ∉ P {\displaystyle S\not \in P} , allora esiste T ⊆ a ∗ {\displaystyle T\subseteq a^{*}} con T ∉ P {\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.

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