Theory of Computing

[vl4d]

Io lancio il sasso, stile TdN for Dummies.
Ecco il primo problema:

Mostrare che il linguaggio
$S={<M>|" M e' una TM che accetta "w^r", per ogni "r\in NN", quando accetta w"}$
e' indecidibile.

[vl4d]

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.

[TomSawyer]

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

[vl4d]

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?

[TomSawyer]

Proprio quella l'idea. Potrebbe sembrare che non si possa fare in tempo lineare, ma quel trucchetto facilita tutto.

[TomSawyer]

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

[vl4d]

Sono gli unici linguaggi tali che loro stessi, oppure i loro complementi,
sono vuoti. (questa e' anche la chiave per il resto dell'esercizio).

[TomSawyer]

Eccone un altro in $O(n)$. Chiamo inversione di due elementi in un array $A$ una coppia $(i,j)$ di indici tali $i<j$ e $A[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.