Esame Completo 16/01/2018

Rispondi
Avatar utente
InformateciBot
Messaggi: 314
Iscritto il: 30/09/2018, 16:33

Per caso qualcuno ha qualche idea su come possano essere risolti?
ECC Gennaio 2018.jpg
ECC Gennaio 2018.jpg (96.22 KiB) Visto 2951 volte

mizipolo
Per il primo credo che possa andare bene [math]. Il fatto che non sia riducibile al suo complementare se non sbaglio è dimostrato nelle dispense. Mentre per quanto riguarda la proprietà di non essere i.i.r.f. puoi vederla così: prendi un indice [math] e un indice [math] (preso ad esempio tramite il padding lemma) tale che [math] calcoli la stessa cosa di [math] e che ovviamente non sta in [math], a quel punto hai trovato due indici di funzioni che calcolano la stessa cosa ma non stanno entrambi in [math]

Edit: [math] deve convergere solo su [math]

OneClaudio
Ottima soluzione grazie, ci avevo pensato subito ma mi sembrava di ricordare che K fosse un i.i.r.f.

Per il secondo andrebbe bene semplicemente far notare che CIRCUIT VALUE e' in P, quindi un qualsiasi problema (per esempio K) che e' in RE non si riduce a CIRCUIT VALUE (P e' contenuto strettamente in RE).
Stessa cosa per far vedere che CIRCUIT VALUE non si riduce ad una classe contenuta strettamente in P, ad esempio non si puo' ridurre ad un problema che richiede sempre solo un passo per essere risolto.

mizipolo
un qualsiasi problema (per esempio K) che e' in RE non si riduce a CIRCUIT VALUE (P e' contenuto strettamente in RE).
Questa cosa, secondo me, non è vera: prendi un qualsiasi problema di P (questo sta in RE, perché sta in REC) e si riduce a CIRCUIT VALUE essendo quest'ultimo P-completo.

Comunque io eviterei di mischiare complessità e calcolabilità. Puoi fare invece semplici considerazioni partendo dalla P completezza di CIRCUIT VALUE, tipo I non può essere un problema di P

OneClaudio
Gia' errore mio ovviamente intendevo un problema in RE ma non in P/NP, come ho detto K andrebbe bene perche' non e' in R, tantomeno in P o NP quindi non lo riduci a CIRCUIT VALUE
Rispondi

Torna a “[ECC] Elementi di calcolabili e complessità”