171 matches
-
ca problema să fie rezolvată sau ca răspunsul să fie da. Pentru a aborda problema P = NP, este util conceptul de NP-completitudine. Problemele NP-complete sunt o mulțime de probleme la care poate fi redusă orice altă problemă NP în timp polinomial, și ale căror soluții pot fi verificate în timp polinomial. Adică, orice problemă NP poate fi ușor transformată în oricare dintre problemele NP-complete. Informal, o problemă NP-completă este o problemă NP care este cel puțin la fel de „grea” ca și orice
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
da. Pentru a aborda problema P = NP, este util conceptul de NP-completitudine. Problemele NP-complete sunt o mulțime de probleme la care poate fi redusă orice altă problemă NP în timp polinomial, și ale căror soluții pot fi verificate în timp polinomial. Adică, orice problemă NP poate fi ușor transformată în oricare dintre problemele NP-complete. Informal, o problemă NP-completă este o problemă NP care este cel puțin la fel de „grea” ca și orice altă problemă din NP. Problemele NP-tari sunt cele care sunt
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
NP-completă este o problemă NP care este cel puțin la fel de „grea” ca și orice altă problemă din NP. Problemele NP-tari sunt cele care sunt cel puțin la fel de grele ca problemele NP, adică toate problemele NP pot fi reduse (în timp polinomial) la ele. Problemele NP-grele nu sunt neapărat în NP, adică nu este nevoie ca ele să aibă soluții verificabile în timp polinomial. De exemplu, este NP-completă conform , deci "orice" instanță a "oricărei" probleme din NP poate fi transformată mecanic în
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
care sunt cel puțin la fel de grele ca problemele NP, adică toate problemele NP pot fi reduse (în timp polinomial) la ele. Problemele NP-grele nu sunt neapărat în NP, adică nu este nevoie ca ele să aibă soluții verificabile în timp polinomial. De exemplu, este NP-completă conform , deci "orice" instanță a "oricărei" probleme din NP poate fi transformată mecanic în timp polinomial într-o instanță a problemei satisfiabilității booleene. Problema satisfiabilității este una din multele astfel de probleme NP-complete. Dacă orice problemă
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
ele. Problemele NP-grele nu sunt neapărat în NP, adică nu este nevoie ca ele să aibă soluții verificabile în timp polinomial. De exemplu, este NP-completă conform , deci "orice" instanță a "oricărei" probleme din NP poate fi transformată mecanic în timp polinomial într-o instanță a problemei satisfiabilității booleene. Problema satisfiabilității este una din multele astfel de probleme NP-complete. Dacă orice problemă NP-completă este în P, atunci ar rezulta că P = NP. Din păcate, s-a demonstrat că multe probleme importante sunt
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
dintre ele. Doar pe baza definiției nu este evident că există probleme NP-complete; dar o problemă NP-completă trivială ar putea fi formulată astfel: dată fiind o descriere a unei mașini Turing M care în mod garantat se oprește în timp polinomial, există o intrare de dimensiuni polinomiale pe care M le va accepta? Ea este în NP deoarece (dată fiind o intrare) este simplu de verificat dacă M acceptă intrarea simulând funcționarea mașinii Turing M; este NP-completă deoarece verificatorul oricărei instanțe
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
nu este evident că există probleme NP-complete; dar o problemă NP-completă trivială ar putea fi formulată astfel: dată fiind o descriere a unei mașini Turing M care în mod garantat se oprește în timp polinomial, există o intrare de dimensiuni polinomiale pe care M le va accepta? Ea este în NP deoarece (dată fiind o intrare) este simplu de verificat dacă M acceptă intrarea simulând funcționarea mașinii Turing M; este NP-completă deoarece verificatorul oricărei instanțe de problemă din NP poate fi
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
este în NP deoarece (dată fiind o intrare) este simplu de verificat dacă M acceptă intrarea simulând funcționarea mașinii Turing M; este NP-completă deoarece verificatorul oricărei instanțe de problemă din NP poate fi codificat ca mașină Turing M de timp polinomial care primește ca intrare soluția de verificat. Apoi întrebarea dacă instanța de problemă primește un răspuns „da” sau un răspuns „nu” se determină prin verificarea existenței unei intrări valide. Prima problemă naturală demonstrată a fi NP-completă a fost . Cum s-
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
număr de probleme succinte (probleme care nu operează pe intrări normale, ci pe o descriere computațională a intrării) sunt cunoscute a fi . Pentru că se poate demonstra că P ≠ , aceste probleme sunt în afara P, și deci necesită timp mai mult decât polinomial. În fapt, prin , ele nu pot fi rezolvate în mod semnificativ mai rapid decât în timp exponențial. Printre exemple se numără găsirea unei strategii perfecte în jocul de șah (pe o tablă "N" × "N") și alte jocuri de masă. Problema
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
izomorfismului grafurilor este în P, NP-completă, sau NP-intermediară. Răspunsul nu este cunoscut, dar se crede că problema cel puțin nu este NP-completă. Dacă izomorfismul grafurilor ar fi NP-completă, s-ar plia la al doilea nivel. Deoarece se crede că ierarhia polinomială nu se pliază la niciun nivel finit, se crede că izomorfismul grafurilor nu este o problemă NP-completă. Cel mai bun algoritm pentru această problemă, datorat lui și , a rulat timp de 2 pentru un graf cu "n" noduri. este problema
Clasele de complexitate P și NP () [Corola-website/Science/336745_a_338074]
-
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]