172 matches
-
factorizare a numerelor întregi, și acest fapt stă la baza celor mai multe sisteme criptografice moderne, cum ar fi algoritmul RSA. Problema factorizarea numerelor întregi problemă este în NP și în (și chiar în UP și co-UP). Dacă problema este NP-completă, ierarhia polinomială se va plia la primul nivel (de exemplu, NP = co-NP). Cel mai cunoscut algoritm pentru factorizarea numerelor întregi este , al cărui timp de rulare este la factorizarea unui număr întreg pe" n "biți. Cu toate acestea, cel mai cunoscut pentru
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
nivel (de exemplu, NP = co-NP). Cel mai cunoscut algoritm pentru factorizarea numerelor întregi este , al cărui timp de rulare este la factorizarea unui număr întreg pe" n "biți. Cu toate acestea, cel mai cunoscut pentru această problemă, , rulează în timp polinomial. Din păcate, acest fapt nu spune prea multe despre clasa de problemă necuantică din care face parte factorizarea. Toată discuția de mai sus pornește de la presupunerea că P înseamnă „ușor” și „nu în P” înseamnă „greu”, o presupunere cunoscută sub
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
greu”, o presupunere cunoscută sub numele de "". Este o ipoteză comună și de o acuratețe rezonabilă din teoria complexității; cu toate acestea, ea are unele limitări. În primul rând, nu este întotdeauna adevărată în practică. Un algoritm teoretic în timp polinomial poate avea factori constanți sau exponenți extrem de mari, ceea ce l-ar face nepractic. Pe de altă parte, chiar dacă o problemă este dovedit a fi NP-completă, și chiar dacă P ≠ NP, încă ar putea exista abordări eficiente pentru rezolvarea problemei pe cazurile
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
scăzută. Un exemplu este algoritmul simplex din programarea liniară, care funcționează surprinzător de bine în practică; în ciuda faptului că are complexitate exponențială pe cel mai rău caz, el rulează pe picior de egalitate cu cei mai cunoscuți algoritmi în timp polinomial. În al doilea rând, există tipuri de calcule care nu sunt conforme cu modelul mașinii Turing pe care sunt definite clasele P și NP, cum ar fi calculul cuantic și . Potrivit sondajelor, mulți informaticieni cred că P ≠ NP. Un motiv
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
fi calculul cuantic și . Potrivit sondajelor, mulți informaticieni cred că P ≠ NP. Un motiv cheie pentru această credință este că, după zeci de ani de studiu al acestor probleme, nimeni nu a fost capabil să găsească un algoritm în timp polinomial pentru vreuna din cele peste 3000 de probleme importante NP-complete cunoscute (a se vedea ). Acești algoritmi au fost căutați cu mult timp înainte de definirea conceptului de NP-completitudine (, printre primele găsite, erau toate problemele bine-cunoscute existente deja la momentul la care
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
teoria complexității se încadrează în una dintre următoarele clasificări, dintre care fiecare se știe că este insuficientă pentru a dovedi că P ≠ NP: Aceste bariere sunt un alt motiv pentru care problemele NP-complete sunt utile: dacă un algoritm în timp polinomial poate fi găsit pentru o problemă NP-completă, acest lucru ar rezolva problema P = NP într-un mod care nu este exclus de rezultatele de mai sus. Aceste bariere i-au condus pe unii informaticieni care să sugereze că problema P
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
unii informaticieni care să sugereze că problema P versus NP poate fi de sistemele axiomatice standard, cum ar fi (nu pot fi dovedite sau infirmate în cadrul acestora). Interpretarea unei independențe ar putea fi că fie nu există algoritm în timp polinomial pentru vreo problemă NP-completă, și o astfel de demonstrație se poate construit în (de exemplu) ZFC, sau că pot exista algoritmi în timp polinomial pentru problemele NP-complete, dar că este imposibil de demonstrat în ZFC că astfel de algoritmi sunt
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
infirmate în cadrul acestora). Interpretarea unei independențe ar putea fi că fie nu există algoritm în timp polinomial pentru vreo problemă NP-completă, și o astfel de demonstrație se poate construit în (de exemplu) ZFC, sau că pot exista algoritmi în timp polinomial pentru problemele NP-complete, dar că este imposibil de demonstrat în ZFC că astfel de algoritmi sunt corecți. Cu toate acestea, dacă poate fi demonstrat, folosind tehnici de genul celor care în prezent sunt cunoscute a fi aplicabile, că problema nu
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
combinație cu relația de ordine, permite efectiv definirea de funcții recursive. Atâta timp cât signatura conține cel puțin un predicat sau o funcție în plus față de relația de ordine, astfel încât cantitatea de spațiu ocupată prin stocarea acestor structuri finite este de 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
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
deoarece P = NP dacă și numai dacă P = PH (întrucât prima ar stabili și că NP = co-NP, care la rândul său implică faptul că NP = PH). Nu se cunoaște niciun algoritm pentru vreo problemă NP-completă care să ruleze în timp polinomial. Există însă algoritmi pentru probleme NP-complete cu proprietatea că, dacă P = NP, atunci algoritmul rulează în timp polinomial (deși cu constante enorme, ceea ce ar face algoritmul nepractic). Următorul algoritm, datorat lui (fără citare), este un astfel de exemplu. El acceptă
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
la rândul său implică faptul că NP = PH). Nu se cunoaște niciun algoritm pentru vreo problemă NP-completă care să ruleze în timp polinomial. Există însă algoritmi pentru probleme NP-complete cu proprietatea că, dacă P = NP, atunci algoritmul rulează în timp polinomial (deși cu constante enorme, ceea ce ar face algoritmul nepractic). Următorul algoritm, datorat lui (fără citare), este un astfel de exemplu. El acceptă limbajul NP-complet SUBSET-SUM. Rulează în timp polinomial dacă și numai dacă P = NP: Dacă, și numai dacă, P
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
cu proprietatea că, dacă P = NP, atunci algoritmul rulează în timp polinomial (deși cu constante enorme, ceea ce ar face algoritmul nepractic). Următorul algoritm, datorat lui (fără citare), este un astfel de exemplu. El acceptă limbajul NP-complet SUBSET-SUM. Rulează în timp polinomial dacă și numai dacă P = NP: Dacă, și numai dacă, P = NP, atunci acesta este un algoritm în timp polinomial care acceptă orice limbaj NP-complet. „Acceptarea” înseamnă că dă răspunsuri „da” în timp polinomial, dar poate rula la nesfârșit atunci când
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
nepractic). Următorul algoritm, datorat lui (fără citare), este un astfel de exemplu. El acceptă limbajul NP-complet SUBSET-SUM. Rulează în timp polinomial dacă și numai dacă P = NP: Dacă, și numai dacă, P = NP, atunci acesta este un algoritm în timp polinomial care acceptă orice limbaj NP-complet. „Acceptarea” înseamnă că dă răspunsuri „da” în timp polinomial, dar poate rula la nesfârșit atunci când răspunsul este „nu” (ceea ce se mai numește și "semi-algoritm"). Acest algoritm este extrem de nepractic, chiar și dacă P = NP. Dacă
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
limbajul NP-complet SUBSET-SUM. Rulează în timp polinomial dacă și numai dacă P = NP: Dacă, și numai dacă, P = NP, atunci acesta este un algoritm în timp polinomial care acceptă orice limbaj NP-complet. „Acceptarea” înseamnă că dă răspunsuri „da” în timp polinomial, dar poate rula la nesfârșit atunci când răspunsul este „nu” (ceea ce se mai numește și "semi-algoritm"). Acest algoritm este extrem de nepractic, chiar și dacă P = NP. Dacă cel mai scurt program care poate rezolva SUBSET-SUM în timp polinomial are lungime de
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
da” în timp polinomial, dar poate rula la nesfârșit atunci când răspunsul este „nu” (ceea ce se mai numește și "semi-algoritm"). Acest algoritm este extrem de nepractic, chiar și dacă P = NP. Dacă cel mai scurt program care poate rezolva SUBSET-SUM în timp polinomial are lungime de "b" biți, atunci algoritmul de mai sus va încerca cel puțin 2-1 alte programe mai întâi. Conceptual vorbind, o "problemă a deciziei" este o problemă care are ca intrare un "w" peste un alfabet Σ, și ieșiri
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
produce răspunsul corect pentru orice șir de intrare de lungime "n" , în cel mult "cn" pași, în cazul în care "k" și "c" sunt constante independente de șirul de intrare, atunci putem spune că problema poate fi rezolvată în "timp polinomial" și o plasăm în clasa P. Formal, P este definită ca o mulțime a tuturor limbajelor care poate fi decise de o mașină Turing deterministă în timp polinomial. Adică, unde și o mașină Turing deterministă în timp polinomial este o
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
de intrare, atunci putem spune că problema poate fi rezolvată în "timp polinomial" și o plasăm în clasa P. Formal, P este definită ca o mulțime a tuturor limbajelor care poate fi decise de o mașină Turing deterministă în timp polinomial. Adică, unde și o mașină Turing deterministă în timp polinomial este o mașină Turing deterministă "M" care satisface următoarele două condiții: NP poate fi definită în mod similar, folosind mașini Turing nedeterministe (în maniera tradițională). Cu toate acestea, o abordare
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
în "timp polinomial" și o plasăm în clasa P. Formal, P este definită ca o mulțime a tuturor limbajelor care poate fi decise de o mașină Turing deterministă în timp polinomial. Adică, unde și o mașină Turing deterministă în timp polinomial este o mașină Turing deterministă "M" care satisface următoarele două condiții: NP poate fi definită în mod similar, folosind mașini Turing nedeterministe (în maniera tradițională). Cu toate acestea, o abordare modernă a definirii clasei NP este utilizarea conceptului de ' și
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
tradițională). Cu toate acestea, o abordare modernă a definirii clasei NP este utilizarea conceptului de ' și "verificator". În mod oficial, NP este definit ca un set de limbaje peste un alfabet finit, care au un verificator care rulează în timp polinomial, unde noțiunea de „verificator” este definită după cum urmează. Fie "L" un limbaj peste un alfabet finit, Σ. "L" ∈ NP dacă, și numai dacă, există o relație binară formula 8 și un număr întreg pozitiv "k" astfel încât următoarele două condiții sunt îndeplinite
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
O mașină Turing care decide "L" se numește un "verificator" pentru "L" și un "y" astfel încât ("x", "y") ∈ "R" se numește un "certificat de apartenență" al lui "x" în "L". În general, un verificator nu trebuie să fie în timp polinomial. Cu toate acestea, pentru ca "L" să fie în NP, trebuie să existe un verificator care rulează în timp polinomial. Fie În mod clar, la întrebarea dacă un anumit "x" este compus este echivalentă cu întrebarea dacă "x" este un membru
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
se numește un "certificat de apartenență" al lui "x" în "L". În general, un verificator nu trebuie să fie în timp polinomial. Cu toate acestea, pentru ca "L" să fie în NP, trebuie să existe un verificator care rulează în timp polinomial. Fie În mod clar, la întrebarea dacă un anumit "x" este compus este echivalentă cu întrebarea dacă "x" este un membru al COMPOSITE. Se poate demonstra că COMPOSITE ∈ NP , verificând că acesta îndeplinește definiția de mai sus (dacă vom identifica
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
O funcție transcendentă este o funcție analitică care nu satisface nicio ecuație polinomială, spre deosebire de . (uneori se pune condiția ca polinoamele să aibă coeficienți raționali.) Cu alte cuvinte, o funcție transcendentă „transcende” algebra prin aceea că nu poate fi exprimată în termenii unui șir finit de de adunare, înmulțire, și extragere de radical. Exemple
Funcție transcendentă () [Corola-website/Science/336921_a_338250]