Polynominen aika, ???

Kts. wikipedia:time complexity.

Ohman

Mä olen ymmärtänyt asian niin, että jos g on pisteen x_0 punkteeratussa ympäristössä määritelty positiivinen funktio, voidaan merkitä O_{x_0}(g) on niiden funktioiden f joukko, jolla f/g on rajoitettu jossain x_0:n ympäristössä. Nyt polynomiaalinen aika kohdassa x_0 tarkoittaa, että f kuuluu joukkoon O_{x_0}(g) jollain polynomilla g.

Kun ei kerrottu haetaanko tarkkaa matemaattista vai millaista selitystä niin tässä yksi:

Ongelma xxx(N) ratkeaa polynomisessa ajassa tarkoittaa sitä, että kun ongelman vaikeutta N kasvatetaan k-kertaiseksi niin ongelman ratkaisemiseen kuluva aika kasvaa verrannollisena johonkin luvun k potenssiin, esimerkiksi tekijään k^2, k^3 tai k^4 (eli aika on polynomi k:n suhteen). Jos ongelma ei ratkea polynomisessa ajassa niin silloin monimutkaisuuden lisääminen tekijällä k voi aiheuttaa ongelman ratkaisemiseen kuluvan ajan kasvamisen eksponentiaalisesti eli tekijällä exp(vakio*k).

Ero ilmenee esimerkiksi siinä, että oikein tehty 32 bittinen salaus on triviaali murtaa kotikoneella, 64 - bittinen salaus murtuu isolla tietokoneella luokkaa kymmenissä vuosissa mutta triviaalia kahdeksan kertaa pidemmällä avaimella (k=8) tehty eli 256 - bittinen ei murru parhaalla supertietokoneella edes maailmankaikkeuden iän kuluessa.