[11 settembre 2024] Complessità

[matypist]

[cornflexxx]

Dimostriamo che $L :=\{\langle x,y\rangle | f^{-1}(x) < y\}$ è decidibile in tempo polinomiale da una $NTM$.

Sia $N$ una $NTM$ che prende in input $\langle x,y\rangle$ e non deterministicamente sceglie una stringa di $n$-bit $w$, successivamente calcola $f(w)$. Se $f(w) \neq x$ allora rifiuta, se $f(w) = x$ verifica che $w<y$ e nel caso sia vero accetta, altrimenti rifiuta.

Quindi $\langle x,y\rangle\in L(N)\iff f^{-1}(x) < y$, segue che $L(N) = L$. Inoltre $L$ computa in spazio polinomiale su ogni ramo di computazione, quindi $L\in NP$. Inoltre possiamo costruire una $NTM$ $\overline{N}$ che decide $\overline{L}$ in tempo polinomiale, la quale semplicemente verificherà che $w \ge y$. Quindi $\overline{L} \in NP\iff L \in coNP$.

Supponiamo che esista $TM$ $M$ che decide $L$ in $O(n^k)$, allora $M$ calcola $f^{-1}(x)$ in tempo polinomiale contraddicendo l'assunto che ciò non sia possibile. Segue che $L\in(NP \cap coNP)/P$.