Theory of Computing
Io lancio il sasso, stile TdN for Dummies.
Ecco il primo problema:
Mostrare che il linguaggio
$S={|" M e' una TM che accetta "w^r", per ogni "r\in NN", quando accetta w"}$
e' indecidibile.
Ecco il primo problema:
Mostrare che il linguaggio
$S={
e' indecidibile.
Risposte
Mmm... provo un ultimo tentativo, magari P vs. NP e' piu' interessante ...
Se $P=NP$ allora ogni $A \in P$, ad eccezione di $\emptyset$ e di $\Sigma^*$,
e' $NP$-completo.
Se $P=NP$ allora ogni $A \in P$, ad eccezione di $\emptyset$ e di $\Sigma^*$,
e' $NP$-completo.
Posto anch'io un problema carino, così c'è più scelta. (anche se è meno "theoretic"). Dato $S \subset {1,...,2n}$ con $|S|=n+1$, trovare un algoritmo che restituisca in output, se presente, una coppia di elementi di $S$ tali che uno divida l'altro.
ps: si può fare anche in $O(n)$.
ps: si può fare anche in $O(n)$.
Su "input" $S = {s_1, \cdots, s_{n+1}}$,
notiamo che ogni $s_i \in S$ puo' essere scritto $s_i=2^m \cdot q$ con $q$ dispari. (*)
Notiamo inoltre che ${1,\cdots, 2n}$ contiene $n$ numeri dispari.
Prepariamo allora $n$ insiemi $S_1, S_3 \cdots, S_{2n-1}$
I)Per ogni $i=1,\cdots, n$ :
1) Poniamo $S_{d} = S_{d}\cup {s_i}$ quando esiste $m$ t.c. $s_i = 2^m\cdot d$
2) Se $|S_d| = 2$, ritorniamo $S_d$, altrimenti andiamo in I)
La complessita' dell'algo e' $O(n)$ se supponiamo
di conoscere gia' la rappresentazione in (*),
altrimenti non sono cosi' sicuro... Di sicuro resta $O(nlog n)$...
Proprio un bel problema comunque, l'idea era questa?
notiamo che ogni $s_i \in S$ puo' essere scritto $s_i=2^m \cdot q$ con $q$ dispari. (*)
Notiamo inoltre che ${1,\cdots, 2n}$ contiene $n$ numeri dispari.
Prepariamo allora $n$ insiemi $S_1, S_3 \cdots, S_{2n-1}$
I)Per ogni $i=1,\cdots, n$ :
1) Poniamo $S_{d} = S_{d}\cup {s_i}$ quando esiste $m$ t.c. $s_i = 2^m\cdot d$
2) Se $|S_d| = 2$, ritorniamo $S_d$, altrimenti andiamo in I)
La complessita' dell'algo e' $O(n)$ se supponiamo
di conoscere gia' la rappresentazione in (*),
altrimenti non sono cosi' sicuro... Di sicuro resta $O(nlog n)$...
Proprio un bel problema comunque, l'idea era questa?
Proprio quella l'idea. Potrebbe sembrare che non si possa fare in tempo lineare, ma quel trucchetto facilita tutto.
"vl4d":
Se $P=NP$ allora ogni $A \in P$, ad eccezione di $\emptyset$ e di $\Sigma^*$,
e' $NP$-completo.
Perché ad eccezione di $\emptyset$ e di $\Sigma^*$? Dovrebbero essere anche loro NPC, se P=NP..
Sono gli unici linguaggi tali che loro stessi, oppure i loro complementi,
sono vuoti. (questa e' anche la chiave per il resto dell'esercizio).
sono vuoti. (questa e' anche la chiave per il resto dell'esercizio).
Eccone un altro in $O(n)$. Chiamo inversione di due elementi in un array $A$ una coppia $(i,j)$ di indici tali $i>A[j]$. Supponendo che l'array contenga solo $0,1,2$, calcolare in $O(n)$ il numero totale di inversioni, con $n$ la dimensione dell'array.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo