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? (Sappiamo che ha un certo effetto, a causa dell'algoritmo di Grover, ma quanto? BQP=P?)
- La non uniformità accelera effettivamente il calcolo?
- Può la 3SAT essere risolta in [math]2^{o(n)}[/math]? [/math]tempo? (L'ipotesi del tempo esponenziale)
- Può kSAT essere risolta in [math]O(2^{0.9999 n})[/math] tempo per tutti i k? (L'ipotesi del tempo esponenziale forte)
- Può 3SUM essere risolto in [math]O(n^{1.99999})[/math] tempo?
- Può ordinare X+Y essere risolto in [math]O(n^2)[/math] tempo? In [math]O(n^{1.99999})[/math] time?
- Può essere risolto in [math]O(n^{2.99999}) [/math] time?
- La congettura dei giochi unici è vera?
- Le proprietà dei grafi monotoni sono evasive?
- I flussi massimi in grafi planari possono essere calcolati in tempo O(n)?
- I flussi massimi in grafi toroidali (indiretti, a capacità unitaria) possono essere calcolati in tempo O(n^{1.49999}[/math]? [Tempo O(n log n)[/math]? O(n) time?
- Esiste un algoritmo implementabile per triangolare i poligoni in O(n) time?
- Esiste un algoritmo implementabile per decidere se un grafico può essere disegnato su un toro senza incroci di bordi in O(n) time? Per grafi di genere 2? Per grafi di larghezza d'albero 4?
- Può una grammatica arbitraria senza contesto di lunghezza essere convertita in forma normale di Chomsky in [math]O(n^{1.9999})[/math] tempo? Tempo [matematico] O(n^{3/2}[/matica]?
- Gli alberi di strombatura sono dinamicamente ottimali? Un qualsiasi albero di ricerca binaria autoregolante online è dinamicamente ottimale? Un albero di ricerca binario autoregolante offline è dinamicamente ottimale?
- Il genere di un nodo può essere calcolato in tempo polinomiale?
- Qual è il quinto numero di Ramsey R(5,5)? Il sesto numero di Ramsey R(6,6)? Il settimo R(7,7)?
- Esiste una dimostrazione verificabile a macchina del teorema della struttura dei grafi di Robertson e Seymour? E il teorema di classificazione per i gruppi semplici finiti?
- Qual è la più piccola macchina di Turing il cui comportamento è indipendente da ZFC?
- E' una generalizzazione naturale di Getting Over It NP-hard? PSPACE-hard? Indecidibile?
- Quante leccate ci vogliono per arrivare al centro di un Tootsie Pop?
E questa è solo informatica teorica.