P (teoria complexității)

Clasa de complexitate P cuprinde problemele de decizie care sunt executate în cel mai rău caz în timp polinomial de către o mașină Turing deterministă.

6 relaţii: Clasă de complexitate, Gradul unui polinom, Mașina Turing deterministă, Mașina Turing nedeterministă, Mașină Turing, NP (teoria complexității).

Clasă de complexitate

În teoria complexității, o clasă de complexitate cuprinde problemele cu complexități similare, unde complexitatea măsoară cantitatea unei anumite resurse, de exemplu timp sau spațiu de memorie, necesară rezolvării problemei.

Nou!!: P (teoria complexității) și Clasă de complexitate · Vezi mai mult »

Gradul unui polinom

În matematică, gradul unui polinom este cel mai mare dintre gradele monoamelor polinomului (adică al termenilor individuali) cu coeficienți diferiți de zero.

Nou!!: P (teoria complexității) și Gradul unui polinom · Vezi mai mult »

Mașina Turing deterministă

Relația de tranziție \scriptstyle \delta a unei mașini Turing specifică acțiunea pe care o execută mașina (de exemplu deplasarea capului de citire la stânga sau la dreapta sau scrierea unui anumit simbol pe bandă) precum și tranziția de stare pe care o efectuează atunci când întâlnește un anumit simbol pe bandă și se află într-o anumită stare interioară.

Nou!!: P (teoria complexității) și Mașina Turing deterministă · Vezi mai mult »

Mașina Turing nedeterministă

Spre deosebire de o mașină Turing deterministă, tranziția \delta unei mașini Turing nedeterministe este o relație între mulțimile \scriptstyle Q\times\Gamma și \scriptstyle Q\times\Gamma\times\ iar nu o funcție.

Nou!!: P (teoria complexității) și Mașina Turing nedeterministă · Vezi mai mult »

Mașină Turing

O reprezentare artistică a unei ''Mașini Turing''. Mașinile Turing sunt mecanisme extrem de elementare de dispozitive de prelucrare a simbolurilor care — în ciuda simplității lor — pot fi adaptate pentru a simula logica oricărui calculator ce poate fi construit.

Nou!!: P (teoria complexității) și Mașină Turing · Vezi mai mult »

NP (teoria complexității)

Clasa de complexitate NP (nedeterminist polinomial) cuprinde problemele de decizie care sunt executate în cel mai rău caz în timp polinomial de către o mașină Turing nedeterministă.

Nou!!: P (teoria complexității) și NP (teoria complexității) · Vezi mai mult »

Redirecționează aici:

P (teoria complexităţii).

Uniunpedie este o hartă concept sau rețea semantică organizat ca o enciclopedie sau dicționar. Acesta oferă o scurtă definiție a fiecărui concept și a relațiilor sale.

Aceasta este o hartă mentală on-line gigant, care servește ca bază pentru diagrame conceptuale. Este libertatea de a folosi și pentru fiecare articol sau document poate fi descărcat. Este un instrument, resursă sau de referință pentru studiu, cercetare, educație, de învățare sau de predare, care pot fi utilizate de către profesori, educatori, elevi sau studenți; pentru lumea academică: pentru școală, primar, secundar, liceu, de mijloc, colegiu, grad tehnic, colegiu, universitate, licență, masterat sau de doctorat; pentru lucrări, rapoarte, proiecte, idei, documentare, studii, sinteze, sau a unei teze. Aici este definiția, explicația, descrierea sau semnificația fiecărei semnificative pe care aveți nevoie de informații, precum și o listă a conceptelor asociate lor, ca un glosar. Disponibil în română, Engleză, Spaniolă, Portugheză, Japonez, Chinez, Limba franceza, Germană, Italiană, Lustrui, Olandeză, Rusă, Arabic, Hindi, Suedez, Ucrainean, Maghiar, Catalan, Ceh, Evrei, daneză, finlandeză, indoneziană, norvegiană, turcă, vietnameză, coreeană, thai, greacă, bulgară, croat, slovacă, lituanian, filipineză, letonă, estonă și slovenă. Mai multe limbi în curând.

Toate informațiile au fost extrase din Wikipedia, și este disponibil sub licența Creative Commons cu atribuire şi distribuire în condiţii identice.

Uniunpedie nu este susținută de sau afiliată cu Fundația Wikimedia.

Google Play, Android și sigla Google Play sunt mărci comerciale deținute de Google Inc.

Politica de confidentialitate