Hardness of Approximation

Una breve introduzione alla teoria dell’inapprossimabilità per problemi appartenenti alla classe NP.

Questo post è stato pubblicato il Domenica, 13 Luglio 2008 alle 3:07 pm ed è archiviato in ICT. Segui i commenti a questo post con il feed RSS 2.0. Puoi lasciare una risposta, o mandare un trackback dal tuo sito.

4 Risposte a “Hardness of Approximation”

  1. antgri Dice:
    Luglio 13, 2008 alle 7:33 pm | Replica

    Oggi hanno parlato in TV di un nuovo calcolatore che svolge in poche ore le computazioni che i computer “veloci” di oggi effettuano in mesi e mesi di lavoro…

    naturalmente sarà solo ad uso militare degli States…

    Che no ci sia qualche sorpresina epr qualcuno dei problemi NP-Complessi?

  2. carlol Dice:
    Luglio 14, 2008 alle 8:03 pm | Replica

    Ne dubito.
    Risolvere un problema NP complesso in tempo polinomiale con una macchina deterministica significherebbe dimostrare l’equivalenza tra le classi P e NP (uno dei sette problemi del millennio per cui sono in palio 1 milione di dollari)…
    Oggi per “rendere veloci” alcune computazioni difficili si utilizza la potenza di migliaia di calcolatori sparsi per il mondo e collegati via internet (esempio Grid Computing)
    In ogni modo mai dire mai…ormai nulla più ci sorprende;-)

  3. antgri Dice:
    Luglio 15, 2008 alle 11:25 am | Replica

    si.. mi pare si chiamano “zombie network”.. alcune reti per sferrare attacchi a sistemi GSM ad esempio…

    Tuttavia se priam u DES o un DES doppio poteveno farsi forte dei loro numerosi bit che lo difendevano da attacchi di forza bruta, con un computer così veloce, attacchi che prima di risolvevano in 1 anno possono risolversi in un giorno…

    questo il senso del mio intervento precedente

  4. carlol Dice:
    Luglio 18, 2008 alle 9:42 am | Replica

    Si, hai perfettamente ragione.
    La sicurezza “assoluta” in informatica non esiste.
    Essa viene valutata in base alle quantità di risorse (computazionali e di tempo) necessarie per scardinare un algoritmo. Il senso è:”se ho probabilità molto ridotte di scardinare un algoritmo…è meglio giocare al superenalotto che ho più probabilità di vincere!”.
    Comunque oggi credo che des, pian piano sostituito da AES, venga utilizzato solo per scambio di chiavi di sessione (chiavi che durano poco nel tempo–>un possibile attaccante ha poco tempo per corrompere l’algoritmo).
    Tra le altre cose, per altri algoritmi, si cominciano ad utilizzare chiavi a 1024 bit.
    Comunque la tua interpretazione è totalmente corretta.
    Quel che oggi è sicuro, domani non potrebbe più esserlo.

Lascia un commento