" Si avvicina il sogno più antico " cit.

Quote:

---

Originally Posted by Kith

ma son tutte cagate dai, il viaggio nel tempo lol

---

oh, ecco uno che la pensa come me :nod:

Quote:

---

Originally Posted by Glasny

Hanno appena dimostrato (se sarà confermato, io 100 pagine di pubblicazione non le leggo) che P != NP, un noto problema informatico la cui soluzione comporta anche il premio di un milione di dollari. Purtroppo questo implica anche che i viaggi nel tempo sono impossibili, quindi mettetevi il cuore in pace.

http://www.scribd.com/doc/35539144/pnp12pt

---

Sarebbe sto problema?? non trovo niente in giro

Quote:

---

Originally Posted by Hardcore

Sarebbe sto problema?? non trovo niente in giro

---

Uno dei più famosi problemi irrisolti in informatica, forse il più famoso, e anche il più importante. Se vuoi un link di wiki http://it.wikipedia.org/wiki/Classi_...t%C3%A0_P_e_NP
Poi se ti interessa consulta un qualsiasi testo informatico di calcolabilità e complessità.

La discussione è già iniziata sul web sulla validità della dimostrazione:
http://rjlipton.wordpress.com/2010/0...-p%E2%89%A0np/

seguimi glasny. Il calcolo delle variabili necessarie a trasportare un sistema di particelle subatomiche da un punto all'altro dello spaziotempo è sicuramente un problema np-hard, perchè ogni particella trasportata cambierebbe il problema in gioco e quindi ad ogni passo dell'algoritmo prenderebbe ancora più tempo del passo precedente, detto in maniera brutale. Ciononostante, il tempo in sè non è detto che esista, è un'astrazione prodotta dall'intelligenza che in vari modi è stata scardinata in primis dalla relatività. Il viaggio nel tempo è un mero viaggio nello spazio, il problema è che non sappiamo cosa sia lo spazio in sè, nè siamo in grado algebricamente di definire cosa siano le dimensioni, se non dei casi banali di una metrica che usiamo a livello macroscopico per misurare ciò che vediamo. Già nell'infinitamente piccolo tale metrica non vale e ne abbiamo dovuta inventare una molto più complessa, creando un mostro chiamato spazio vettoriale sulle variabili aleatorie.

In sostanza, non siamo proprio in grado di dire se il viaggio nel tempo sia possibile o no. E' come dire che Dio non esiste, è un'affermazione non falsificabile alla luce delle nostre conoscenze.

[OT]
Per quanto riguarda i problemi NP complessi, è molto carino avere una dimostrazione che P!=NP, ma come congettura era già stata formulata. In natura esiste già un algoritmo in grado di risolvere tali problemi in un tempo finito, solo che non è implementabile nè su una macchina di Touring, tantomeno su una macchina quantistica. Ma non spoilero, lascio a te la risposta e la spiegazione ;).
[/OT]

Quote:

---

Originally Posted by marlborojack

seguimi glasny. Il calcolo delle variabili necessarie a trasportare un sistema di particelle subatomiche da un punto all'altro dello spaziotempo è sicuramente un problema np-hard, perchè ogni particella trasportata cambierebbe il problema in gioco e quindi ad ogni passo dell'algoritmo prenderebbe ancora più tempo del passo precedente, detto in maniera brutale. Ciononostante, il tempo in sè non è detto che esista, è un'astrazione prodotta dall'intelligenza che in vari modi è stata scardinata in primis dalla relatività. Il viaggio nel tempo è un mero viaggio nello spazio, il problema è che non sappiamo cosa sia lo spazio in sè, nè siamo in grado algebricamente di definire cosa siano le dimensioni, se non dei casi banali di una metrica che usiamo a livello macroscopico per misurare ciò che vediamo. Già nell'infinitamente piccolo tale metrica non vale e ne abbiamo dovuta inventare una molto più complessa, creando un mostro chiamato spazio vettoriale sulle variabili aleatorie.

In sostanza, non siamo proprio in grado di dire se il viaggio nel tempo sia possibile o no. E' come dire che Dio non esiste, è un'affermazione non falsificabile alla luce delle nostre conoscenze.

[OT]
Per quanto riguarda i problemi NP complessi, è molto carino avere una dimostrazione che P!=NP, ma come congettura era già stata formulata. In natura esiste già un algoritmo in grado di risolvere tali problemi in un tempo finito, solo che non è implementabile nè su una macchina di Touring, tantomeno su una macchina quantistica. Ma non spoilero, lascio a te la risposta e la spiegazione ;).
[/OT]

---

Sul discorso della fantascienza/viaggio nel tempo uno si può ancora inventare tutto quello che vuole, e infatti la deduzione che i viaggi non siano possibili perchè non è possibile in natura una macchina che risolva problemi np-completi in tempo p resta una congettura. Però mi sembra ragionevole, perchè da delle restrizioni ben precise sulla definizione fisica di tempo. E' una situazione strana in cui un concetto apparentemente del tutto astratto poi porta a delle conclusioni per il mondo reale.

I problemi in questione non sono NP complessi (che intendi per complessi, ardui ?) ma completi e sono tutti risolvibili in un tempo finito. Non so se volevi sapere se avevo le basi della materia ma fino a lì ci arrivo. I problemi NP-completi sono in teoria eseguibili in tempo P su una macchina di touring non deterministica, che però non può fisicamente esistere. Finora P != NP era solo una congettura e anzi alcuni invece supponevano il contrario, e ci sono state pubblicazioni che tentavano di dimostrarlo, poi rivelatesi sbagliate però. Questa che ho linkato invece a parte alcune critiche che sembrano correggibili, sembra averci preso. Le conseguenze sono molteplici, sia per i futuri calcolatori, che per la crittografia nel presente, che solitamente si basa proprio su un problema np-completo.

Quote:

---

Originally Posted by Glasny

Sul discorso della fantascienza/viaggio nel tempo uno si può ancora inventare tutto quello che vuole, e infatti la deduzione che i viaggi non siano possibili perchè non è possibile in natura una macchina che risolva problemi np-completi in tempo p resta una congettura. Però mi sembra ragionevole, perchè da delle restrizioni ben precise sulla definizione fisica di tempo. E' una situazione strana in cui un concetto apparentemente del tutto astratto poi porta a delle conclusioni per il mondo reale.

I problemi in questione non sono NP complessi (che intendi per complessi, ardui ?) ma completi e sono tutti risolvibili in un tempo finito. Non so se volevi sapere se avevo le basi della materia ma fino a lì ci arrivo. I problemi NP-completi sono in teoria eseguibili in tempo P su una macchina di touring non deterministica, che però non può fisicamente esistere. Finora P != NP era solo una congettura e anzi alcuni invece supponevano il contrario, e ci sono state pubblicazioni che tentavano di dimostrarlo, poi rivelatesi sbagliate però. Questa che ho linkato invece a parte alcune critiche che sembrano correggibili, sembra averci preso. Le conseguenze sono molteplici, sia per i futuri calcolatori, che per la crittografia nel presente, che solitamente si basa proprio su un problema np-completo.

---

LOL glasny, NP complessi in quanto la loro complessità, ovvero la teoria che li racchiude, è NP ovvero non-polynomial. E comunque i problemi al massimo possono essere duri come un NP ;). Sul tempo "finito" intendevo invece polinomiale ovviamente, non ho riletto. E ora anche basta con gli OT :hidenod:

Quote:

---

Originally Posted by marlborojack

LOL glasny, NP complessi in quanto la loro complessità, ovvero la teoria che li racchiude, è NP ovvero non-polynomial. E comunque i problemi al massimo possono essere duri come un NP ;). Sul tempo "finito" intendevo invece polinomiale ovviamente, non ho riletto. E ora anche basta con gli OT :hidenod:

---

Eh permetti che scritto così non si capiva un cazzo, potevo interpretarlo ma vista la materia meglio essere precisi. Ci sono anche problemi indecidibili, che sono peggio dei NP. Ad esempio se un programma termina. Una cosa che si può far notare è che anche se in generale un problema NP ha un runtime maggiore per essere risolto, non è sempre vero, infatti se la cardinalità dell'input è inferiore a un dato limite, avere un polinomio che ne so con x^1000 vs un exponenziale 2^x porta a un tempo P > NP. Ora qualcuno bravo in matematica calcoli il valore per x per cui 2^x > x^1000 (ok è facile su).

Quote:

---

Originally Posted by Glasny

Hanno appena dimostrato (se sarà confermato, io 100 pagine di pubblicazione non le leggo) che P != NP, un noto problema informatico la cui soluzione comporta anche il premio di un milione di dollari. Purtroppo questo implica anche che i viaggi nel tempo sono impossibili, quindi mettetevi il cuore in pace.

http://www.scribd.com/doc/35539144/pnp12pt

---

Quando si saprà se è o meno confermato? Voglia di leggere tutto pari a 0.

Quote:

---

Originally Posted by marlborojack

E quale sarebbe l'implicazione sui viaggi nel tempo? Oltretutto non implica che i problemi NP non siano risolvibili, bensì che i problemi NP non appartengono alla classe polinomiale.

---

Si e che l'acqua è bagnata non lo dici? :O
I problemi NP SONO risolvibili, stiamo parlando di problemi decidibili eh.

Il problema è QUANTO ci metti a risolverli. Ignoro poi come dovrebbe funzionare un computer quantistico ergo non so se sia o meno in grado di risolvere problemi NP in tempi umani. Magari riescono a realizzare una macchina di turing non deterministica sfruttando i quanti e allora tutti i problemi (decidibili) del mondo sono risolti :shrug:

Quote:

---

Originally Posted by Hardcore

Sarebbe sto problema?? non trovo niente in giro

---

Ma te mica studi informatica scusa? lol -_-

Quote:

---

Originally Posted by Axet

Quando si saprà se è o meno confermato? Voglia di leggere tutto pari a 0.


Ma te mica studi informatica scusa? lol -_-

---

Ci vorrà qualche mese, ora che gli altri scienziati cercano errori e l'autore li corregge, alla fine o si arriva a una dimostrazione accettata oppure si scova un errore non correggibile.

Non credo che studi informatica Hardcore, almeno lo spero. Però il problema interessa anche i non informatici, anche perchè si va dalla crittografia ai programmi per gestire il traffico aereo e anzi la maggior parte delle applicazioni interessanti si basano su problemi np-completi e loro soluzioni approssimate.

Quote:

---

Originally Posted by Axet

Si e che l'acqua è bagnata non lo dici? :O

---

:sneer:

Quote:

---

Originally Posted by Glasny

Ci vorrà qualche mese, ora che gli altri scienziati cercano errori e l'autore li corregge, alla fine o si arriva a una dimostrazione accettata oppure si scova un errore non correggibile.

Non credo che studi informatica Hardcore, almeno lo spero. Però il problema interessa anche i non informatici, anche perchè si va dalla crittografia ai programmi per gestire il traffico aereo e anzi la maggior parte delle applicazioni interessanti si basano su problemi np-completi e loro soluzioni approssimate.

---

A me pareva facesse ingegneria informatica, magari ricordo male.. cmq sticazzi :nod:

Ti ricordo cmq che tutta la classificazione dei problemi come P, NP o NP-completi è rivolta solo e soltanto a problemi decisionali. Il che vuol dire che, anche se dovessero dimostrare in futuro che P = NP, per problemi enumerativi (che sono i più interessanti) le cose sono diverse

Quote:

---

Originally Posted by Axet

A me pareva facesse ingegneria informatica, magari ricordo male.. cmq sticazzi :nod:

Ti ricordo cmq che tutta la classificazione dei problemi come P, NP o NP-completi è rivolta solo e soltanto a problemi decisionali. Il che vuol dire che, anche se dovessero dimostrare in futuro che P = NP, per problemi enumerativi (che sono i più interessanti) le cose sono diverse

---

Se il metodo usato nella dimostrazione viene confermato, vedrai che si estende anche per dimostrare altre cose più o meno correlate.

Nono io intendevo proprio che, nel caso venga dimostrato il contrario rispetto a quel paper, cioè che P = NP, ancora non avremmo in mano un cazzo di niente. I problemi decisionali sono meno complessi dei problemi enumerativi.

Prendiamo SAT che è quello che è servito per dimostrare l'esistenza degli NP-completi. Il problema decisionale chiede, data una formula espressa secondo le regole di SAT, se questa sia o meno soddisfacibile. Se lo è risponde true, se non lo è risponde false. Questo problema è NP-completo ed è come abbiamo appena visto un problema decisionale. Pensala in un'altra maniera: data la formula non voglio più sapere se sia soddisfacibile o meno, voglio sapere quali sono tutte le configurazioni che la soddisfano. Risulta evidente che il secondo problema risulti molto più pesante del primo.

Difatti questa variante di SAT non è manco NP-completa, bensì NP-hard (in quanto non è decisionale ma enumerativa)

Quote:

---

Originally Posted by Axet

Nono io intendevo proprio che, nel caso venga dimostrato il contrario rispetto a quel paper, cioè che P = NP, ancora non avremmo in mano un cazzo di niente. I problemi decisionali sono meno complessi dei problemi enumerativi.

Prendiamo SAT che è quello che è servito per dimostrare l'esistenza degli NP-completi. Il problema decisionale chiede, data una formula espressa secondo le regole di SAT, se questa sia o meno soddisfacibile. Se lo è risponde true, se non lo è risponde false. Questo problema è NP-completo ed è come abbiamo appena visto un problema decisionale. Pensala in un'altra maniera: data la formula non voglio più sapere se sia soddisfacibile o meno, voglio sapere quali sono tutte le configurazioni che la soddisfano. Risulta evidente che il secondo problema risulti molto più pesante del primo.

Difatti questa variante di SAT non è manco NP-completa, bensì NP-hard (in quanto non è decisionale ma enumerativa)

---

Non si diceva np-arduo (l'ho studiato anni fa magari a quei tempi si usava ancora l'italiano) ?

Dubito ormai si dimostri il contrario, se leggi almeno l'abstract e le critiche ti rendi conto che probabilmente corregge tutto e la questione viene chiusa. Lo so che non tutti i problemi in NP sono NP-completi ma nella pratica mi dici perchè i problemi NP-ardui sarebbero più interessanti ? Visto che nelle applicazioni pratiche ne trovo quanti ne voglio di esempi di problemi np-completi, ma quelli ardui non mi pare.

Perchè con np e np-completi ma come anche con p, p-space e np-space (dove tra l'altro per questi due è stata già dimostrata l'ugaglianza) si parla di problemi decisionali. Parafrasando, tu chiedi al computer se il calcolo che hai fatto è giusto e lui ti dice si o no.
Sarebbe più interessante sapere direttamente la risposta alla domanda piuttosto che trovare la risposta e poi chiedere se sia o meno corretta.

Questi rimangono problemi non polinomiali, non c'è un cazzo da fare.. il dubbio sull'uguaglianza tra P e NP verteva sul fatto che essendo problemi decisionali magari c'era qualche modo, ancora sconosciuto, per rendere la computazione più veloce al fine di trovare la risposta. Ma se devi invece enumerare tutte le possibilità, non ci sono cazzi che tengano le devi vagliare tutte.. e per problemi non polinomiali queste sono, appunto, non polinomiali.

edit:
np-hard, np-difficile e np-arduo sono sinonimi