Informateci

- dimostrare che [math]EXT è non ricorsivo
- [math]EXT è un [math]I.I.R.F.? (risposta: si)
- dimostrazione del Teorema di Rice
- [math]NP \subseteq EXP come ci si arriva? quindi dimostrare il Teorema 3.3.6.

Testo dell'esercizio:


Si determini una funzione <math><mi>f</mi></math> calcolabile totale tale che
<math>
<mrow>
<mi>I</mi>
<mo>=</mo>
<mrow>
<mo form="prefix">{</mo>
<mi>i</mi>
<mo>|</mo>
<msub>
<mi>&phi;</mi>
<mi>i</mi>
</msub>
<mo>=</mo>
<msub>
<mi>&phi;</mi>
<mrow>
<mi>f ...

Sto provando a fare l'esercizio presente a pagina 2 :
dimostrare che

I = \{\,x \mid \varphi_x(x) = \varphi_x(x+30) \,\}

non è un I.I.R.F.

Per definizione,
I \mbox{ è un I.I.R.F. se e solo se } \forall_{x,y}\mbox{. se } x\in I \mbox{ e } \varphi_x=\varphi_y \mbox{ allora } y\in I
L'idea a ...

Joker
Sappiamo che R U R = R perchè entrambi si possono decidere in tempo finito. Cosa succede però con l'unione infinita di insiemi ricorsivi?

MindFlyer
Può essere sia ricorsiva che non ricorsiva.
Esempio: l'unione di {n} per ogni n naturale è ovviamente tutto \mathbb N , e quindi ricorsivo ...

Joker

Nelle dispense del Degano, per dimostrare che SAT è NP-completo scrive:

Poichè CIRCUIT SAT \leqslant SAT, ci basta dimostrare che CIRCUIT SAT è NP-completo,

Perchè ci basta dimostrare questo?
Io sapevo che un problema A, completo per una certa classe S, non dice nulla su un altro ...

Probabilmente ti riferisci al compitino della Paganelli, sul gruppo telegram qualcuno ha messo il testo, contattami su telegram @Hungerys

Questo è il post originale https://old.informateci.it/discussion/9 ... -operativa

Venduto.

Dato che negli ultimi anni è cambiato qualcosa sugli argomenti affrontati nello scritto e nell'orale ho creato questo thread a parte.
Prima del 2016 c'erano Bevilacqua-Del Corso-Menchi, quindi quelle domande non sono state riportate.

Domande di Giugno/Luglio 2016:

- Dimostrazione teorema del ...

EDIT: VENDUTO

Vendo libro usato Reti di calcolatori. Un approccio top-down 1 mar 2013 di Behrouz A. Forouzan (Autore), Firoeuz Mosharraf (Autore), G. D'Angelo (Traduttore), G. Maselli (Traduttore)
Prezzo: 25 euro
Per altre informazioni contattatemi su Telegram (Username: Hungerys) o qui sul ...