Problemi radi

Introduzione[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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.