[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. Essendo questa una risposta in grado di farci vincere un milione di dollari e un premio Turing, la vedo leggermente difficile da dimostrare per uno studente universitario.

Proviamo quindi a dimostrare che k-PATH non sia in NL. Dobbiamo solo trovare un modo per dimostrare che non può esistere un certificato verificabile in una determinata quantità di spazio, processo che potremmo utilizzare anche per separare tutte le classi di tempo da tutte le classi di spazio situate sopra di loro, altra domanda in grado di far vincere un premio Turing.

---

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$.

[cornflexxx]

Credo che con cammino intenda un percorso da $s$ a $t$ che ammetta vertici ripetuti (si può usare il termine simple path o cammino elementare per cammini con vertici che non si ripetono), in questo caso è possibile costruire un verificatore con certificato read-once polinomiale. Il certificato è proprio una lista di vertici $\boldsymbol{v} = \langle v_1,v_2,\dots, v_k\rangle$ , che rappresenta un cammino. Il nostro verificatore $V$ deve :

1. verificare che $v_1 = s$ in spazio $O(\log \ n)$
2. per ogni $v_i$ e $v_{i+1}$ nel certificato deve verificare che esista $(v_i,v_{i+1})\in E$ in spazio $O(\log \ n)$
3. verificare che $v_k = t$ in spazio $O(\log\ n)$
4. verificare che la lunghezza del cammino sia esattamente $k$, questo richiede la memorizzazione di un contatore in $O(\log k)$.

Il verificatore scorre il certificato da sinistra a destra una sola volta e compie tutte le mosse dalla 1 alla 4 con complessità spaziale $O(\log \ n \cdot k)$. Se esegue tutti i passi accetta, altrimenti se uno fallisce allora rifiuta.

[Exyss]

@cornflexxx Anche interpretandola in questo modo, ci sono comunque due buchi

1. Occhio che $O(\log \ k)$ è polinomiale rispetto al size dell'input, non logaritmico. Questo poiché il valore $k$ in input è rappresentato da $\lceil \log \ k \rceil$ bit. L'algoritmo quindi non richiede spazio logaritmico, bensì polinomiale. La difficoltà di verificare in spazio logaritmico tutti i problemi NP completi di questo tipo è proprio il fatto che la dimensione del valore $k$ in input renda praticamente impossibile controllare che siano $k$ gli elementi richiesti poiché un counter è inutilizzabile.

2. (Qui userò il termine walk per intendere un cammino con vertici ripetuti per distinguere le due cose) Se potessimo risolvere il problema k-walk in spazio logaritmico, potremmo risolvere il problema at-most-k-path (anch'esso NP completo) poiché l'esistenza di una walk da $s$ a $t$ con $k$ nodi implica sempre l'esistenza di un path da $s$ a $t$ con massimo $k$ nodi.