[6 febbraio 2023] Complessità

[matypist]

[aflaag]

Si noti che $$\textsf{NP} = \textsf{NP-Complete} := \textsf{NP} \cap \textsf{NP-Hard} \iff \textsf{NP} \subseteq \textsf{NP-Hard} \iff \forall L, L' \in \textsf{NP} = \textsf{P} \quad L' \leq_\mathrm P L$$ dunque il problema equivale a dimostrare che ogni problema in $\textsf P$ è riducibile polinomialmente ad ogni altro problema in $\textsf P$.

Siano dunque $L_1, L_2 \in \textsf P$; per loro definizione, esistono macchine di Turing $M_1$ ed $M_2$ tali da deciderli rispettivamente in tempo polinomiale. Allora, prese $x \in L_2$ e $y \notin L_2$, si consideri una macchina di Turing $M$ che, su input $w \in \Sigma^*$, computa come segue:

• $M$ computa $M_1(w)$;
• se $M_1$ accetta, $M$ scrive $x$ sul suo nastro e termina;
• se $M_1$ rifiuta, $M$ scrive $y$ sul suo nastro e termina;

Allora, chiamando $f : \Sigma^* \to \Sigma^*$ la funzione computabile che $M$ rappresenta, per costruzione di $M$ si ha che $w \in L_1 \implies f(w) = x \in L_2$ e $w \notin L_1 \implies f(w) = y \notin L_2$ e dunque $$w \in L_1 \iff f(w) \in L_2$$ Questo dimostra che $f$ è una riduzione da $L_1$ a $L_2$, e poiché $M_1$ decide $L_1$ in tempo polinomiale, ed il costo di $M$ è interamente determinato da $M_1$, segue che $f$ è una riduzione polinomiale di $L_1$ a $L_2$, e dunque segue la tesi.

[Exyss]

Il primo punto è in realtà completamente INSENSATO visto che il professor Venturi è un po' tanto ignorante nella materia stessa che insegna.

Il problema "k-PATH" così come descritto da lui è in realtà NP-Completo, in quanto possiamo facilmente creare la catena di riduzioni SAT $\leq_m^p$ HAMPATH $\leq_m^p$ k-PATH. Per tanto, abbiamo che:

• Se k-PATH è in NL allora k-PATH è in P visto che NL $\subseteq$ P, quindi abbiamo dimostrato che P = NP
• Se k-PATH non è in NL allora abbiamo trovato un problema che è in P ma non in NL, quindi abbiamo dimostrato che NL $\neq$ P

Entrambe sono domande da milioni di dollari in palio, quindi la vedo molto difficile

---

Per il secondo punto la dimostrazione di @aflaag è corretta, anche se l'affermazione da dimostrare è vera solo se assumiamo che $\varnothing, \Sigma^{*}$ non siano in nessuna classe computazionale. Difatti, per i due linguaggi $\varnothing$ e $\Sigma^{*}$ è impossibile che essi siano riducibili ad un altro linguaggio o che un altro linguaggio sia riducibile ad essi (segue dalla definizione stessa di riducibilità tramite mappatura).

Senza questa precisazione, la dimostrazione avrebbe un buco: ponendo $L_2 = \varnothing$ non può esistere la stringa $x$ mentre ponendo $L_2 = \Sigma^*$ non può esistere la stringa $y$.