Pseudopolynomisk algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 22 september 2015; kontroller kräver 5 redigeringar .

Pseudopolynomisk algoritm - i teorin om beräkningskomplexitet är detta en polynomalgoritm som endast uppvisar en exponentiell karaktär för mycket stora värden av numeriska parametrar.

En mer rigorös definition ser ut så här. Låt vara någon funktion som specificerar värdet på den numeriska parametern för det enskilda problemet . Om det finns flera sådana parametrar kan antingen det maximala eller det genomsnittliga värdet tas som värde, och om problemet inte har några numeriska parametrar alls (till exempel graffärgning, schack, etc.), då . En algoritm kallas pseudopolynom om den har en kostnadsberäkning , där finns något polynom i två variabler. $M(z)$ $z$ $M(z)$ $M(z)=0$ $T_{max}(z)=O(P(|z|,M(z)))$ $P$

En polynomalgoritm är också pseudopolynom (med ett polynom oberoende av det andra argumentet), men det omvända är inte fallet. Pseudopolynomalgoritmer, formellt relaterade till exponentiella algoritmer, fungerar i praktiken som polynom i alla fall, förutom mycket stora värden på den numeriska parametern.

Litteratur

Drozdov S.N. Kombinatoriska problem och delar av beräkningskomplexitetsteori: Lärobok. - Taganrog: Publishing House of TRTU, 2000. - S. 58.