Perché polinomiale di tempo si chiama “efficiente”?

Question

Perché in informatica qualsiasi complessità che è al più polinomiale è considerato efficiente?

Per qualsiasi applicazione pratica ^(a) , algoritmi con la complessità $ n ^ {\ log n} $ sono il modo più veloce di algoritmi che vengono eseguiti in tempo, diciamo, $ n ^ {80} $, ma la prima è considerata inefficiente mentre il secondo è efficiente. Dov'è la logica?!

^{(a) Si supponga, per esempio, il numero di atomi presenti nell'universo è di circa $ 10 ^ {80} $.}

Answer 1

Un altro punto di vista sulla "efficienza" è che il tempo polinomiale ci permette di definire una nozione di "efficienza" che non dipende da modelli di macchine. In particolare, c'è una variante della tesi di Church-Turing chiamato "efficace Church-Turing Tesi" che dice che qualsiasi problema che viene eseguito in un tempo polinomiale su sul tipo di modello di macchina sarà anche eseguito in un tempo polinomiale su un altro modello di macchina altrettanto potente.

Questa è una dichiarazione debole alla tesi generale CT, ed è 'sorta di' violata da entrambi gli algoritmi randomizzati e algoritmi quantistici, ma non è stata violata nel senso di poter risolvere un problema NP-hard in poli- tempo modificando il modello di macchina.

Questa è in definitiva il motivo per cui un tempo polinomiale è una nozione popolare in theoryCS. Tuttavia, la maggior parte delle persone si rendono conto che questo non riflette "efficacia pratica". Per ulteriori informazioni su questo, post di Dick Lipton sul ' galattico algoritmi ' è un grande letto.

Answer 2

In teoria, ci preoccupiamo per il comportamento asintotico, e descriviamo classi di problemi e algoritmi in base al loro comportamento asintotico. La parola chiave qui è asintotica . $ O (n ^ {80}) $ è più veloce di $ O (n ^ {\ log n}) $ asintoticamente, cioè, a partire da $ n> 1208925819614629174706176 $ (che tra l'altro si chiama:! Septillion), unità che coefficienti costanti, e nessun termini ordine inferiore.

In pratica, tuttavia, si presta attenzione ad entrambi esponenti e coefficienti costanti. In pratica, i formati di input non possono crescere a septillions, quindi, sì, $ n ^ {\ log n} $ a tutti gli effetti sarà una scelta superiore a $ n ^ {80} $. Altri fattori anche la materia nelle pratiche:. Parallelismo, modelli di accesso di memoria (ad esempio località)

Per esempio, la maggior parte delle librerie per intero la moltiplicazione, ad esempio GMP attuerà una miscela di algoritmi, e selezionare algoritmo inferiore sulla base delle dimensioni di input selezionare la praticamente algoritmi superiori in base alle dimensioni di ingresso, se questi algoritmi potrebbero essere asintoticamente inferiore. Alcuni asintoticamente algoritmi "inferiori" sarà più veloce su alcune dimensioni di ingresso, e viene selezionata negli algoritmi ottimali.

Un altro esempio, l'algoritmo di moltiplicazione di matrice veloce noto è Coppersmith-Winograd algoritmo che corre in $ O (n ^ {2,3737}) $ (ci sono i recenti miglioramenti; più qui ). Tuttavia, non è mai stato attuato perché (1) E 'difficile (2) il coefficiente costante è gigantesco. Tutti i pacchetti di algebra lineare usa il meno ottimale di Strassen .

TL;. DR cure teoria per il comportamento asintotico per confrontare algoritmi come limite della dimensione dell'input va arbitrariamente grandi numeri

Answer 3

Questa risposta sarà guardare il contesto "grande immagine" della tua domanda. L'informatica è in realtà una scienza relativamente giovane e un po 'aperta e che ancora non hanno risposte grandi o anche buoni ad alcune domande di base e fondamentali. La questione fondamentale "ciò che è efficiente calcolato" è o esattamente o circa formalizzata in CS (a seconda del parere) come il famoso P vs problema NP (o strettamente correlata P vs EXPTIME problema), e la sua ancora Apri dopo più di quattro decenni di essere introdotto inizialmente da Cook / Levin ~ 1970 ed intenso lavoro dai mondi più grandi scienziati informatici (e molti matematici sono interessati anche nel problema come fondamentale).

Quindi, in altre parole, anche con un approssimativa definizione di "efficienza", come il tempo P, e uno dei riconoscimenti scientifici più alto valore - vale a dire $ premio 1M attaccato al problema per oltre 10yrs - del computer la scienza non può nemmeno dimostrare che alcuni problemi (vicino a questa borderline) devono o non devono avere algoritmi efficienti (Primario). Pertanto, la definizione esatta del tempo "efficace" più precisa di P non è necessario né possibile in questo momento. Se / quando il P vs NP congettura è risolta in un modo o l'altro, una definizione più rigorosa di "efficiente" può o presumibilmente sarà possibile.

Inoltre, si potrebbe pensare che la definizione Primario di "efficiente" potrebbe anche essere un po ' "sciatta", e la maggior parte degli scienziati informatici sarebbe probabilmente d'accordo, e la quasi totalità di loro pensano P vs NP congettura è della massima importanza per determinazione, al punto che si potrebbe anche considerare questa affermazione o l'osservazione così banale .... in altre parole, per così dire, il suo un work in progress / stiamo lavorando su di esso . (Infatti informatici tradizionale si spingono fino, scherzando solo a metà, per riferirsi routine per il vuoto e mancanza di progressi / separazioni definitive imbarazzante .)

In realtà c'è anche un strettamente legato / significativamente più forte congettura di P vs NP, ovvero NP vs P / poli, che, inoltre, non può essere risolto dalla scienza informatica in questo momento. si ipotizza che i problemi NP-tempo non possono essere risolti qualsiasi circuiti "P-size", cioè non ancora limitato a quei circuiti che possono essere creati da algoritmi / Turing macchine.

Per quanto riguarda P quanto sia difficile vs NP può essere - c'è qualche ragione solida per pensare, può essere almeno così difficile come molto vecchio congettura di Riemann in matematica (ora 1.5 secolo vecchia), perché entrambi hanno avuto lo stesso premio $ 1 milione per oltre un decennio, e nessuno dei due è stato ancora risolto / prima.

Quindi, in altre parole, di definire con precisione ciò che gli algoritmi sono davvero "efficiente" è in realtà una delle più importanti e più difficili esistenti problemi aperti nel campo della scienza e della matematica teorica .

In realtà, la questione di "ciò che è efficace calcolata" è in realtà ancora più sottile, perché c'è una variante della tesi Church-Turing chiamato CT tesi P-tempo, e non è noto se quantici effettivamente viola di esso. Con risultato svolta di Shor di P-tempo QM, factoring considerato una svolta drammatica in questa ricerca. In altre parole, il problema di ciò che è efficace calcolata in realtà discende plausibilmente fino principi fisici profondi, e si riferisce al fatto quantum computing può calcolare più efficiente rispetto computazione classica, che è anche un problema generalmente aperti in CS teorica e fisica avanzata.

Quindi, si può anche aggiungere che P vs NP & la questione del calcolo efficiente può essere di importanza cruciale o fondamentale per in - oltre a CS e la matematica -. fisica

[1] P vs NP problema, wikipedia

[2] problemi premio Millenium

[3] P / classe Poly, wikipedia

[4] di Shor algoritmo

Answer 4

algoritmi di tempo polinomiale sono considerati efficaci solo in confronto con il periodo più duro non polinomiale in particolare la cosiddetta NP-completo. Vedere l'immagine: Eulero diagramma per P, NP, NP-completo, e NP-hard serie di problemi .