210 matches
-
răspuns, dar dacă unui calculator i se prezintă un posibil răspuns, el îl poate verifica rapid. Clasa de astfel de probleme care pot fi "verificate" în timp polinomial se numește NP, care înseamnă „timp nedeterminist polinomial”. Fie sproblema sumei elementelor submulțimilor, un exemplu de problemă ușor de verificat, dar al cărui răspuns poate fi dificil de calculat. Dată fiind o mulțime de numere întregi, există vreo submulțime nevidă a ei ale cărei elemente au suma 0? De exemplu, există o submulțime
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
timp polinomial se numește NP, care înseamnă „timp nedeterminist polinomial”. Fie sproblema sumei elementelor submulțimilor, un exemplu de problemă ușor de verificat, dar al cărui răspuns poate fi dificil de calculat. Dată fiind o mulțime de numere întregi, există vreo submulțime nevidă a ei ale cărei elemente au suma 0? De exemplu, există o submulțime a mulțimii {−2, −3, 15, 14, 7, −10} ale cărei elemente adunate dau 0? Răspunsul este „da, pentru că submulțimea {−2, −3, −10, 15} are suma zero
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
submulțimilor, un exemplu de problemă ușor de verificat, dar al cărui răspuns poate fi dificil de calculat. Dată fiind o mulțime de numere întregi, există vreo submulțime nevidă a ei ale cărei elemente au suma 0? De exemplu, există o submulțime a mulțimii {−2, −3, 15, 14, 7, −10} ale cărei elemente adunate dau 0? Răspunsul este „da, pentru că submulțimea {−2, −3, −10, 15} are suma zero” și poate fi rapid verificat efectuând trei adunări; dar nu există niciun algoritm cunoscut
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
o mulțime de numere întregi, există vreo submulțime nevidă a ei ale cărei elemente au suma 0? De exemplu, există o submulțime a mulțimii {−2, −3, 15, 14, 7, −10} ale cărei elemente adunate dau 0? Răspunsul este „da, pentru că submulțimea {−2, −3, −10, 15} are suma zero” și poate fi rapid verificat efectuând trei adunări; dar nu există niciun algoritm cunoscut care să găsească această submulțime în timp polinomial (există doar unul care îl găsește în timp exponențial, și care
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
15, 14, 7, −10} ale cărei elemente adunate dau 0? Răspunsul este „da, pentru că submulțimea {−2, −3, −10, 15} are suma zero” și poate fi rapid verificat efectuând trei adunări; dar nu există niciun algoritm cunoscut care să găsească această submulțime în timp polinomial (există doar unul care îl găsește în timp exponențial, și care efectuează 2-n-1 încercări). Un astfel de algoritm există doar dacă P = NP; deci această problemă este în NP (rapid verificabilă) dar nu neapărat în P (rapid
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
algoritm există doar dacă P = NP; deci această problemă este în NP (rapid verificabilă) dar nu neapărat în P (rapid rezolvabilă). Soluția problemei P = NP ar determina dacă problemele ce se pot verifica în timp polinomial, ca problema sumei elementelor submulțimii, pot fi și rezolvate în timp polinomial. Dacă se dovedește că P ≠ NP, ar însemna că există probleme din NP (cum ar fi problemele ) care sunt mai greu de calculat decât de verificat: ele nu pot fi rezolvate în timp
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
fapt polinomială în raport cu numărul de elemente în structură, aceasta caracterizează în mod precis P. În mod similar, NP este un set de limbaje exprimabile într-o existențială—adică logică de ordinul al doilea restricționată prin excluderea peste relații, funcții, și submulțimi. Limbajele din , , corespund întregii logici de ordinul al doilea. Astfel, la întrebarea „este P o submulțime proprie a lui NP” poate fi reformulată ca „este logica de ordinul al doilea existențială capabilă să descrie limbaje (cu structură finită și liniar
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
similar, NP este un set de limbaje exprimabile într-o existențială—adică logică de ordinul al doilea restricționată prin excluderea peste relații, funcții, și submulțimi. Limbajele din , , corespund întregii logici de ordinul al doilea. Astfel, la întrebarea „este P o submulțime proprie a lui NP” poate fi reformulată ca „este logica de ordinul al doilea existențială capabilă să descrie limbaje (cu structură finită și liniar ordonată cu signatură netrivială) pe care nu le poate descrie logica de ordinul întâi cu combinator
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
de operațiuni rămân algebrice sau chiar . Teoria a fost dezvoltată mai departe de Gotthold Eisenstein (), Eduard Heine, și alții. Următoarele funcții sunt transcendente: Deși calcularea mulțimii excepționale a unei funcții date nu este ușoară, se știe că, dată fiind "orice" submulțime a mulțimii numerelor algebrice, notată cu "A", există o functie transcendentă ƒ a cărei mulțime excepțională este "A". Submulțimea poate fi și toată mulțimea numerelor algebrice. Acest lucru implică automat că există funcții transcendente care produc numere transcedente numai atunci când
Funcție transcendentă () [Corola-website/Science/336921_a_338250]
-
Următoarele funcții sunt transcendente: Deși calcularea mulțimii excepționale a unei funcții date nu este ușoară, se știe că, dată fiind "orice" submulțime a mulțimii numerelor algebrice, notată cu "A", există o functie transcendentă ƒ a cărei mulțime excepțională este "A". Submulțimea poate fi și toată mulțimea numerelor algebrice. Acest lucru implică automat că există funcții transcendente care produc numere transcedente numai atunci când primește numere transcendente. a demonstrat și că există funcții transcendente pentru care nu există demonstrații ale transcendenței lor în
Funcție transcendentă () [Corola-website/Science/336921_a_338250]