Buone notizie per pony-express

Di pwd | Pubblicato: 30 Dicembre 2006

Questo dice di aver risolto il "Traveling Salesman Problem" in tempo polinomiale (Bum!) Vi sembrerà roba da poco, ma invece è uno dei problemi scientifici più studiati. Funziona così: metti che devi partire dalla pizzeria, portare la pizza a tre clienti e tornare alla pizzeria, e sai qual è la strada più breve per fare il giro. Metti che ora ti aggiungo un altro cliente: quanto ci metti a ricalcolare il giro più breve? Ecco, si dice che ci voglia un tempo ¨non-polinomiale¨ (cioè molto lungo). Invece, secondo questo, basta un tempo ¨polinomiale¨ (un po' più corto). Sarà vero? Se avete la voglia e il tempo, date un'occhiata e controllate se bara.

Questo inserimento è stato pubblicato in scienze. Metti un segnalibro su permalink. Sia i commenti che i trackback sono chiusi.

3 Commenti

  1. kysucix
    Pubblicato il 31 Dicembre 2006 alle 11:45 am | Permalink

    E comunque se mai verra’ il giorno vorro’ vedere i titoloni in prima pagina su tutti i quotidiani:
    P = NP
    haha
    ciao
    kysu

  2. kysucix
    Pubblicato il 31 Dicembre 2006 alle 11:41 am | Permalink

    punto it non org:
    http://babbage.sissa.it/abs/cs.CC/0609005%C2%A8

  3. mauro
    Pubblicato il 31 Dicembre 2006 alle 1:17 am | Permalink

    mi sa che hai dimenticato qualcosa nel link all’articolo 😉