Quali sono i problemi "più difficili" utilizzando il tempo polinomiale?

Di recente ho letto a seminar work che dice:Quali sono i problemi "più difficili" utilizzando il tempo polinomiale?

L'algoritmo di matching [per i grafici generali] può essere esteso al caso ponderata, che sembra essere uno dei "più difficili" problemi ottimizzazione combinatoria che possono essere risolto in tempo polinomiale.

immediatamente la seguente domanda è venuta in mente:

Sai altri problemi "P-hard"?

Per ora mi piacerebbe definire P-hard come: "Un algoritmo polinomiale è stato trovato molto tardi (dopo il 1950) nella letteratura per quel problema". (O come si potrebbe definire "difficile" meglio se esiste già un algoritmo deterministico che risolve il problema in tempo polinomiale?)

fonte

2010-02-13 Karussell

Vorrei chiedere problemi con un limite inferiore alto in P. – ebo

IMHO un limite non può e non deve essere confrontato * attraverso * diversi tipi di algoritmi o cosa intendi con limite inferiore? – Karussell

Probabilmente vero, ma non è nemmeno una questione molto scientifica ;-) Limite inferiore: il problema ha un limite inferiore di Omega (n ** x). – ebo

In realtà ci sono problemi "P-completi", il che significa che a tutti gli altri problemi che possono essere calcolati in tempo polinomiale può essere ridotto. Vedi http://en.wikipedia.org/wiki/P-complete.

fonte

2010-02-13 20:52:22

Grazie! Ci sono molte cose che posso imparare ... posso accettare la risposta da più di una? – Karussell

No, non puoi. E dovresti tenere aperta la tua domanda per circa un giorno, così le persone hanno la possibilità di vederlo. – ebo

Primes is in P.

fonte

2010-02-13 20:43:37

+1 Perché questa è stata la prima risposta che ho pensato dopo aver letto la domanda. – Nixuz

Bello! Grazie! A proposito: questo ha un effetto sulla crittografia? – Karussell

ah, ok. il "Come pratico !?" la sezione ha già risposto :-) – Karussell

Un altro "duro" problema P risolve "programmazione lineare":

http://en.wikipedia.org/wiki/Linear_programming#Algorithms

fonte

2010-02-13 20:57:47 Guy

The Assignment Problem che può essere risolto in O (n) dal modificato Hungarian Algorithm.

fonte

2010-02-13 23:12:40

ok molto simile al problema che ho citato ... solo per i grafici bipartiti.A proposito, è più vecchio del 1950 ;-) vedi wikipedia: "Nel 2006, fu scoperto che Carl Gustav Jacobi aveva risolto il problema degli incarichi nel 19 ° secolo, e pubblicato postumo nel 1890 in latino." – Karussell

Se si desidera piegare leggermente le regole, quindi pseudo-polynomial time algorithms sono le "più difficili" che è possibile risolvere in "tempo polinomiale".

Un classico esempio di algoritmo pseudo-polinomiale è la soluzione di programmazione dinamica O(nW) su knapsack problem.

fonte

2010-02-28 20:03:26 polygenelubricants

Quali sono i problemi "più difficili" utilizzando il tempo polinomiale?

risposta

Problemi correlati