← Glossario Termine
Exponential Time Hypothesis
Un presupposto ampiamente accettato in informatica secondo cui alcuni enigmi logici difficili non possono essere risolti rapidamente nel peggiore dei casi.
Lo Exponential Time Hypothesis afferma che per un famoso tipo di puzzle, chiamato SAT (trovare valori che rendono vera un’affermazione logica), non esiste una scorciatoia intelligente. Nel peggiore dei casi, il tempo necessario raddoppia con ogni variabile aggiuntiva, il che diventa impossibile molto rapidamente.
Nessuno lo ha dimostrato, ma centinaia di articoli di ricerca presumono che sia vero e si basano su di esso. Se qualcuno lo smentisse davvero, quegli articoli perderebbero fondamento, anche se i loro risultati potrebbero essere ancora giusti.
Citato in