Quali sono i problemi irrisolti dell’informatica?
Ci sono migliaia, se non milioni, di problemi aperti nell’informatica. Eccone una dozzina così su due piedi. Il nondeterminismo accelera effettivamente la computazione? (P=NP?) I problemi risolvibili con poco spazio possono essere risolti rapidamente? (P = PSPACE?) La casualità accelera effettivamente il calcolo? (RP=P? BPP=P?) Quanto lo sfruttamento del calcolo quantistico velocizza effettivamente il calcolo? … Leggi tutto