Perché studiare la teoria della complessità?

Question

Sono un dilettante nello studio degli algoritmi.Per un po’ ho avuto una domanda scottante, Perché studiamo la teoria della complessità in informatica?Il motivo per cui lo chiedo è perché gli algoritmi con una migliore complessità asintotica non sono sempre più veloci ai fini pratici, anzi possono essere assurdamente più lenti.Perché non sviluppare invece una teoria che meglio si adatti alle esigenze pratiche della ricerca scientifica e dell’industria?

Ad esempio, è noto che è possibile sviluppare un algoritmo per determinare una partita a scacchi perfetta $O(1)$, poiché il numero di partite di scacchi legali su una griglia 8×8 è delimitato dall'alto.Tuttavia, ho sentito che questo algoritmo impiegherebbe più tempo dell'età dell'universo per terminare.Ciò solleva la domanda: perché la teoria della complessità?Mi sembra che il campo sia fondamentalmente imperfetto e gli informatici dovrebbero utilizzare un approccio migliore per lo studio degli algoritmi.

(Nota:Le mie più sincere scuse ai ricercatori del settore.☻)

Answer 1

Questa non è una domanda semplice e non dovresti aspettarti una risposta semplice.Ci sono una serie di domande simili in questo spazio:perché studiamo il tempo di esecuzione asintotico?perché utilizziamo l'analisi asintotica del tempo di esecuzione per analizzare gli algoritmi?perché studiamo la teoria della complessità?Ognuno di questi ha più risposte;non c’è una sola ragione per cui lo facciamo, e persone diverse possono avere ragioni diverse.

L'analisi asintotica del tempo di esecuzione presenta vantaggi e svantaggi.Hai individuato con precisione uno degli svantaggi:un buon tempo di esecuzione asintotico non garantisce un buon tempo di esecuzione nella pratica.Ma se ti concentri solo su un singolo vantaggio o svantaggio non otterrai il quadro completo dei punti di forza e di debolezza di quello stile di analisi.Alcuni dei vantaggi sono che l'analisi è relativamente trattabile, non è specifica per una particolare architettura, fornisce informazioni utili sulla scalabilità e, almeno in parte, ha un potere predittivo utile nell'identificare i colli di bottiglia algoritmici.Ad esempio, la differenza tra a $O(n^2)$ algoritmo temporale e a $O(n \log n)$ l'algoritmo temporale può spesso essere significativo, anche se ignoriamo i fattori costanti.Alcuni degli svantaggi sono che i fattori costanti possono essere importanti, gli effetti della gerarchia della cache e della memoria possono essere molto importanti ma vengono ignorati dall'analisi asintotica del tempo di esecuzione e (come qualsiasi metrica) l'ottimizzazione esclusivamente per il tempo di esecuzione asintotico può portare a risultati assurdi di scarsa praticità. utilità (cfr algoritmi galattici E La legge di Goodhart).

Penso che sia utile esaminare anche l'alternativa.Ti incoraggio a esplorare l'alternativa all'analisi asintotica del tempo di esecuzione e ad elaborare ciò che proporresti al suo posto.Se non si tenta di elaborare una proposta concreta, è facile presumere che non sarà poi così difficile trovare qualcosa di meglio...ma quando sei costretto a impegnarti in qualcosa di specifico, potresti scoprire che è più impegnativo di quanto ti aspettassi.Ad esempio, ti incoraggio a familiarizzare con l'analisi di Knuth del tempo di esecuzione dell'algoritmo MESCOLARE nella sua serie TAOCP.Lì esegue un'analisi concreta del tempo di esecuzione, senza asintotici, tenendo conto dei fattori costanti.Se ti costringi a esaminarne i dettagli, ne scoprirai rapidamente gli svantaggi:è estremamente noioso, molto specifico per una particolare architettura di computer e spesso non molto più illuminante.

Allo stesso modo potremmo discutere ciascuno degli altri argomenti - ad esempio, perché o perché non studiare la teoria della complessità - e scopriresti che anche loro hanno delle sfumature.

Voglio anche sottolineare che la comunità della teoria e degli algoritmi è ampia, con una gamma di stili di lavoro diversi.Sembra che tu stia mettendo tutto insieme in una pila, ma c'è uno spettro di lavoro:alcuni di essi sono super-teorici e lontani dalla pratica, altri sono altamente pratici e motivati ​​da problemi concreti e possono avere un impatto immediato, e c'è una gamma di lavori in vari punti tra questi estremi.Penso che sia importante capire che nella comunità teorica c'è del lavoro di grande rilevanza pratica o che ha avuto un impatto notevole, così come c'è lavoro molto più teorico e non motivato da un impatto a breve termine.

Dato che hai chiesto quadri teorici incentrati sul soddisfare le esigenze del settore, potresti essere interessato anche a Parola RAM modello, algoritmi che ignorano la cache, e il memoria esterna parallela modello.

Ti incoraggio vivamente a leggere le seguenti risorse, poiché sono strettamente correlate alla tua domanda: Perché il tempo polinomiale è detto "efficiente"?, Spiegare la rilevanza della complessità asintotica degli algoritmi per la pratica di progettazione di algoritmi, Giustificazione per trascurare i fattori costanti in Big O.