Polinomial Algorithm -
Definiția formală
Algoritmul este identificat cu o mașină Turing deterministă. care calculează răspunsul pe bandă la cuvântul de intrare de la un alfabet Σ de intrare. Rularea TM timp (x), algoritmul cu un cuvânt de intrare fix x este numărul de cicluri ale mașinii Turing de lucru de la început pentru a opri mașina. Complexitatea funcției calculate de o mașină Turing, este o funcție care depinde de lungimea discursului de intrare și egal cu timpul maxim de funcționare a mașinii pe toate cuvintele de intrare de lungime fixă:
.
Dacă funcția f există o mașină Turing M astfel încât CM (n) Conform tezei Bisericii - Turing. orice algoritm imaginabil poate fi realizat printr-o mașină Turing. Pentru orice limbaj de programare, puteți defini o clasă de P, în acest mod (înlocuind definiția unei mașini Turing pentru punerea în aplicare a limbajului de programare). În cazul în care compilator, care a implementat algoritmul încetinește executarea algoritmului în polinomial (adică momentul algoritmului pe masina Turing este mai mică decât o performanță polinomial timp a limbajului de programare), definirea claselor P pentru limba și pentru mașinile Turing sunt aceleași. cod limbaj de asamblare permite conversia la o mașină Turing cu o ușoară încetinire în polinomul, și din moment ce toate limbile existente permit compilați de asamblare (din nou, cu o încetinire polinom), definiția clasa P pentru mașini Turing și pentru orice limbaj de programare existente sunt aceleași. Uneori, o clasă de P au în vedere o clasă mai restrânsă de funcții, și anume clasa de predicate (funcții). În acest caz, yazykomL. care recunoaște predicatul este un set de cuvinte, în care predicatul este 1. Limbajul clasa P este limba pentru care se recunosc predicate lor de clasa P. Evident, în cazul în care L1 și L2 sunt limbile în clasa P, atunci uniunea lor, intersecție și suplimente, de asemenea, fac parte din clasa P. Clasa P este una din clasele înguste de complexitate. Algoritmi care îi aparțin, de asemenea, fac parte din clasa NP. Clasa de BPP (ca permițând punerea în aplicare a unui polinom cu eroare zero), PSpace clasei (deoarece zona de lucru pe o mașină Turing este întotdeauna mai mică decât timpul), clasa P / Poli (pentru a demonstra acest protocol utilizează conceptul de mașină, care este modificat într-un circuit Boolean de polinom dimensiune). Pentru mai mult de 30 de ani rămâne nerezolvată problema egalității claselor P și NP. Dacă acestea sunt egale, atunci orice problemă din clasa NP poate fi rezolvată rapid (în timp polinomial). Cu toate acestea, comunitatea științifică este înclinată spre un răspuns negativ la această întrebare. În plus, nu a fost dovedită și severitatea includerii în clasele mai mari, de exemplu, în PSPACE, dar egalitatea P și PSpace se uită la acest moment este foarte îndoielnic. Exemple de algoritmi P clasă sunt standard plus algoritmi întreg, înmulțire, împărțire, luând restul de divizare, matrice de multiplicare. Elucidarea grafic și altele. Există mai multe probleme pentru care a fost găsit algoritm polinomial, dar nu dovedit, că nu există. Prin urmare, nu se cunoaște dacă aceste probleme aparțin clasei P. Iată câteva dintre ele: Algoritmul Diniz - algoritm polinomial pentru identificarea debitul maxim în rețeaua de transport, propus în 1970, israelian (fost română) om de știință Efim Dinits. Timpul este complexitatea. Obțineți această evaluare permite introducerea ... ... Wikipedia Algoritmul Diffie - algoritmul Diffie-Hellman (engleză Diffie Hellman, DH.) Algoritm care permite cele două părți pentru a obține cheia secretă partajată folosind neprotejat de la ascultare, dar protejat de canalul de substituție. Această cheie poate fi folosit ... Wikipedia Pseudopolynomial algoritm - algoritm polinomial care prezintă natura exponențială numai la valori foarte mari ale parametrilor numerici. O definiție mai riguroasă este după cum urmează. Fie M (z) - o funcție care stabilește valoarea parametrului numeric în mod individual ... ... Wikipedia Un algoritm probabilist - (. Din eroarea delimitată engleză, probabilist, polinomul) în teoria clasa algoritmi de complexitate BPP se numește clasa predicat, rapid (în timp polinomial) calculabil și să dea un răspuns cu o probabilitate mare (și, prin timpul donând, puteți realiza ... Wikipedia algoritmi programabile - Lista de servicii de articole create pentru a coordona dezvoltarea temei. Acest avertisment nu ... Stabilim Wikipedia Testul Agrawal - În testul de informatică Agrawal Kayala Saxena (sau testul AKS) este un test determinist primality polinom propus de oamenii de știință indieni Manindroy Agrawal (ing.) Și cei doi studenți Neeraj Kayal (Wikipedia în limba engleză ... Discrete logaritm - (DLOG) problema inversării funcției în grupul multiplicativ de finit. Cel mai adesea problema logaritmului discret în grupul multiplicativ tratate inele de reziduuri sau câmpuri finite, precum și grupul de puncte ale unui eliptic ... ... Wikipedia Logaritmul discretă - Logaritmul discretă (DLOG) - Obiectivul tratamentului funcției gx la un grup multiplicativ finit G. Problema cea mai comuna logaritm este considerată în grupul floppy elementelor inversabile ale reziduului a inelului, în multiplicativ ... ... WikipediaO definiție mai restrânsă
Clasa P incluse în alte clase
Exemple de clasa algoritmilor P
Probleme pentru care algoritmul polinomial timp nu poate fi găsit
importanță practică
Vezi ce „algoritm polinomial“ în alte dicționare: