Pseudopolynomialgoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 22. syyskuuta 2015 tarkistetusta versiosta . tarkastukset vaativat 5 muokkausta .

Pseudopolynomialgoritmi - laskennallisen monimutkaisuuden teoriassa tämä on polynomialgoritmi, jolla on eksponentiaalinen luonne vain erittäin suurille numeeristen parametrien arvoille.

Tarkempi määritelmä näyttää tältä. Olkoon jokin funktio, joka määrittää yksittäisen tehtävän numeerisen parametrin arvon . Jos tällaisia parametreja on useita, arvoksi voidaan ottaa joko maksimi- tai keskiarvo, ja jos tehtävässä ei ole lainkaan numeerisia parametreja (esim. graafin väritys, shakki jne.), niin . Algoritmia kutsutaan pseudopolynomiksi, jos sillä on kustannusarvio , jossa on jokin polynomi kahdessa muuttujassa. $M(z)$ $z$ $M(z)$ $M(z)=0$ $T_{max}(z)=O(P(|z|,M(z)))$ $P$

Polynomialgoritmi on myös pseudopolynomi (toisesta argumentista riippumaton polynomi), mutta päinvastainen tilanne ei ole. Pseudopolynomialgoritmit, jotka liittyvät muodollisesti eksponentiaalisiin algoritmeihin, toimivat käytännössä polynomeina kaikissa tapauksissa, lukuun ottamatta erittäin suuria numeerisen parametrin arvoja.

Kirjallisuus

Drozdov S.N. Kombinatoriset ongelmat ja laskennallisen kompleksiteorian elementit: Oppikirja. - Taganrog: Publishing House of TRTU, 2000. - S. 58.