Valerio Di Stefano - Minchia, Signor Tenente!

HOME PAGE - PRIVACY POLICY - CONTACTS

Web Analytics
WIKIPEDIA FOR SCHOOLS: English - Spanish - French - Portuguese
 Polynomial time - Wikipedia, the free encyclopedia

Polynomial time

From Wikipedia, the free encyclopedia

PopAds.net - The Best Popunder Adnetwork

In computational complexity theory, polynomial time refers to the computation time of a problem where the time, m(n), is no greater than a polynomial function of the problem size, n. Any given abstract machine will have a complexity class corresponding to the problems which can be solved in polynomial time on that machine.

Written mathematically, m(n) = O(nk) where k is a constant (which may depend on the problem).

Mathematicians sometimes use the notion of "polynomial time on the length of the input" as a definition of a "fast" computation, as opposed to "super-polynomial time", which is anything slower than that. Exponential time is one example of a super-polynomial time.

The complexity class of decision problems that can be solved on a deterministic sequential machine in polynomial time is known as P. The class of decision problems that can be verified in polynomial time is known as NP. Equivalently, NP is the class of decision problems that can be solved in polynomial time on a non-deterministic Turing machine (NP stands for Nondeterministic Polynomial time).

Polynomial time is the smallest time-complexity class on a deterministic machine which is robust in terms of machine model changes, and is the smallest class closed under composition of subproblems.

Strongly polynomial time means further that the running time is independent of the numerical data size and thus depends only on the inherent dimensions of the problem.

[edit] Subclasses of polynomial time

[edit] See also

Retrieved from "http://en.wikipedia.org../../../p/o/l/Polynomial_time.html"

STATIC WIKIPEDIA JUNE 2008 on wikipedia2006.classicistranieri.com

aa - ab - af - ak - als - am - an - ang - ar - arc - as - ast - av - ay - az - ba - bar - bat_smg - bcl - be - be_x_old - bg - bh - bi - bm - bn - bo - bpy - br - bs - bug - bxr - ca - cbk_zam - cdo - ce - ceb - ch - cho - chr - chy - co - cr - crh - cs - csb - cu - cv - cy - da - de - diq - dsb - dv - dz - ee - el - eml - en - eo - es - et - eu - ext - fa - ff - fi - fiu_vro - fj - fo - fr - frp - fur - fy - ga - gan - gd - gl - glk - gn - got - gu - gv - ha - hak - haw - he - hi - hif - ho - hr - hsb - ht - hu - hy - hz - ia - id - ie - ig - ii - ik - ilo - io - is - it - iu - ja - jbo - jv - ka - kaa - kab - kg - ki - kj - kk - kl - km - kn - ko - kr - ks - ksh - ku - kv - kw - ky - la - lad - lb - lbe - lg - li - lij - lmo - ln - lo - lt - lv - map_bms - mdf - mg - mh - mi - mk - ml - mn - mo - mr - mt - mus - my - myv - mzn - na - nah - nap - nds - nds_nl - ne - new - ng - nl - nn - no - nov - nrm - nv - ny - oc - om - or - os - pa - pag - pam - pap - pdc - pi - pih - pl - pms - ps - pt - qu - quality - rm - rmy - rn - ro - roa_rup - roa_tara - ru - rw - sa - sah - sc - scn - sco - sd - se - sg - sh - si - simple - sk - sl - sm - sn - so - sr - srn - ss - st - stq - su - sv - sw - szl - ta - te - tet - tg - th - ti - tk - tl - tlh - tn - to - tpi - tr - ts - tt - tum - tw - ty - udm - ug - uk - ur - uz - ve - vec - vi - vls - vo - wa - war - wo - wuu - xal - xh - yi - yo - za - zea - zh - zh_classical - zh_min_nan - zh_yue - zu

STATIC WIKIPEDIA MARCH 2008 on wikipeda2006classicistranieri.com
aa, ab, af, ak, als, am, an, ang, ar, arc, as, ast, av, ay, az, ba, bar, bat_smg, be, bg, bh, bi, bm, bn, bo, bpy, br, bs, bug, bxr, ca, cbk_zam, cdo, ce, ceb, ch, cho, chr, chy, closed_zh_tw, co, cr, cs, csb, cu, cv, cy, da, de, diq, dv, dz, ee, el, eml, en, eo, es, et, eu, fa, ff, fi, fiu_vro, fj, fo, fr, frp, fur, fy, ga, gd, gl, glk, gn, got, gu, gv, ha, haw, he, hi, ho, hr, hsb, ht, hu, hy, hz, ia, id, ie, ig, ii, ik, ilo, io, is, it, iu, ja, jbo, jv, ka, kg, ki, kj, kk, kl, km, kn, ko, kr, ks, ksh, ku, kv, kw, ky, la, lad, lb, lbe, lg, li, lij, lmo, ln, lo, lt, lv, map_bms, mg, mh, mi, mk, ml, mn, mo, mr, ms, mt, mus, my, mzn, na, nah, nap, nds, nds_nl, ne, new, ng, nl, nn, no, nov, nrm, nv, ny, oc, om, or, os, pa, pag, pam, pap, pdc, pi, pih, pl, pms, ps, pt, qu, rm, rmy, rn, ro, roa_rup, roa_tara, ru, ru_sib, rw, sa, sc, scn, sco, sd, se, searchcom, sg, sh, si, simple, sk, sl, sm, sn, so, sq, sr, ss, st, su, sv, sw, ta, te, test, tet, tg, th, ti, tk, tl, tlh, tn, to, tokipona, tpi, tr, ts, tt, tum, tw, ty, udm, ug, uk, ur, uz, ve, vec, vi, vls, vo, wa, war, wo, wuu, xal, xh, yi, yo, za, zea, zh, zh_classical, zh_min_nan, zh_yue, zu.

STATIC WIKIPEDIA APRIL 2007 on wikipeda2006classicistranieri.com
aa, ab, af, ak, als, am, an, ang, ar, arc, as, ast, av, ay, az, ba, bar, bat_smg, be, bg, bh, bi, bm, bn, bo, bpy, br, bs, bug, bxr, ca, cbk_zam, cdo, ce, ceb, ch, cho, chr, chy, closed_zh_tw, co, cr, cs, csb, cu, cv, cy, da, de, diq, dv, dz, ee, el, eml, en, eo, es, et, eu, fa, ff, fi, fiu_vro, fj, fo, fr, frp, fur, fy, ga, gd, gl, glk, gn, got, gu, gv, ha, haw, he, hi, ho, hr, hsb, ht, hu, hy, hz, ia, id, ie, ig, ii, ik, ilo, io, is, it, iu, ja, jbo, jv, ka, kg, ki, kj, kk, kl, km, kn, ko, kr, ks, ksh, ku, kv, kw, ky, la, lad, lb, lbe, lg, li, lij, lmo, ln, lo, lt, lv, map_bms, mg, mh, mi, mk, ml, mn, mo, mr, ms, mt, mus, my, mzn, na, nah, nap, nds, nds_nl, ne, new, ng, nl, nn, no, nov, nrm, nv, ny, oc, om, or, os, pa, pag, pam, pap, pdc, pi, pih, pl, pms, ps, pt, qu, rm, rmy, rn, ro, roa_rup, roa_tara, ru, ru_sib, rw, sa, sc, scn, sco, sd, se, searchcom, sg, sh, si, simple, sk, sl, sm, sn, so, sq, sr, ss, st, su, sv, sw, ta, te, test, tet, tg, th, ti, tk, tl, tlh, tn, to, tokipona, tpi, tr, ts, tt, tum, tw, ty, udm, ug, uk, ur, uz, ve, vec, vi, vls, vo, wa, war, wo, wuu, xal, xh, yi, yo, za, zea, zh, zh_classical, zh_min_nan, zh_yue, zu.

STATIC WIKIPEDIA DECEMBER 2006 on wikipeda2006classicistranieri.com
aa, ab, af, ak, als, am, an, ang, ar, arc, as, ast, av, ay, az, ba, bar, bat_smg, be, bg, bh, bi, bm, bn, bo, bpy, br, bs, bug, bxr, ca, cbk_zam, cdo, ce, ceb, ch, cho, chr, chy, closed_zh_tw, co, cr, cs, csb, cu, cv, cy, da, de, diq, dv, dz, ee, el, eml, en, eo, es, et, eu, fa, ff, fi, fiu_vro, fj, fo, fr, frp, fur, fy, ga, gd, gl, glk, gn, got, gu, gv, ha, haw, he, hi, ho, hr, hsb, ht, hu, hy, hz, ia, id, ie, ig, ii, ik, ilo, io, is, it, iu, ja, jbo, jv, ka, kg, ki, kj, kk, kl, km, kn, ko, kr, ks, ksh, ku, kv, kw, ky, la, lad, lb, lbe, lg, li, lij, lmo, ln, lo, lt, lv, map_bms, mg, mh, mi, mk, ml, mn, mo, mr, ms, mt, mus, my, mzn, na, nah, nap, nds, nds_nl, ne, new, ng, nl, nn, no, nov, nrm, nv, ny, oc, om, or, os, pa, pag, pam, pap, pdc, pi, pih, pl, pms, ps, pt, qu, rm, rmy, rn, ro, roa_rup, roa_tara, ru, ru_sib, rw, sa, sc, scn, sco, sd, se, searchcom, sg, sh, si, simple, sk, sl, sm, sn, so, sq, sr, ss, st, su, sv, sw, ta, te, test, tet, tg, th, ti, tk, tl, tlh, tn, to, tokipona, tpi, tr, ts, tt, tum, tw, ty, udm, ug, uk, ur, uz, ve, vec, vi, vls, vo, wa, war, wo, wuu, xal, xh, yi, yo, za, zea, zh, zh_classical, zh_min_nan, zh_yue, zu.

STATIC WIKIPEDIA NOVEMBER 2006 on wikipeda2006classicistranieri.com
aa, ab, af, ak, als, am, an, ang, ar, arc, as, ast, av, ay, az, ba, bar, bat_smg, be, bg, bh, bi, bm, bn, bo, bpy, br, bs, bug, bxr, ca, cbk_zam, cdo, ce, ceb, ch, cho, chr, chy, closed_zh_tw, co, cr, cs, csb, cu, cv, cy, da, de, diq, dv, dz, ee, el, eml, en, eo, es, et, eu, fa, ff, fi, fiu_vro, fj, fo, fr, frp, fur, fy, ga, gd, gl, glk, gn, got, gu, gv, ha, haw, he, hi, ho, hr, hsb, ht, hu, hy, hz, ia, id, ie, ig, ii, ik, ilo, io, is, it, iu, ja, jbo, jv, ka, kg, ki, kj, kk, kl, km, kn, ko, kr, ks, ksh, ku, kv, kw, ky, la, lad, lb, lbe, lg, li, lij, lmo, ln, lo, lt, lv, map_bms, mg, mh, mi, mk, ml, mn, mo, mr, ms, mt, mus, my, mzn, na, nah, nap, nds, nds_nl, ne, new, ng, nl, nn, no, nov, nrm, nv, ny, oc, om, or, os, pa, pag, pam, pap, pdc, pi, pih, pl, pms, ps, pt, qu, rm, rmy, rn, ro, roa_rup, roa_tara, ru, ru_sib, rw, sa, sc, scn, sco, sd, se, searchcom, sg, sh, si, simple, sk, sl, sm, sn, so, sq, sr, ss, st, su, sv, sw, ta, te, test, tet, tg, th, ti, tk, tl, tlh, tn, to, tokipona, tpi, tr, ts, tt, tum, tw, ty, udm, ug, uk, ur, uz, ve, vec, vi, vls, vo, wa, war, wo, wuu, xal, xh, yi, yo, za, zea, zh, zh_classical, zh_min_nan, zh_yue, zu.