problemă polinomial și polinomul - studopediya

Să presupunem că / (u) și g

Noi numim problema polinomului (problema polinomial), în cazul în care aparține O (/ (u)), unde f

Căutarea de activități care aparțin P, este una dintre principalele probleme ale tehnicii de calcul, întrucât este strâns legată cu întrebări despre dacă există o soluție practică pentru problemele. Într-adevăr, problema non-P, sunt caracterizate de foarte lungă durată, chiar și pentru factorii de producție mici. De exemplu, ne imaginăm o sarcină care se realizează în 2 etape „Expresia exponențială 2“ nu este limitată de nici un polinom. Într-adevăr, în cazul în care f

Să considerăm un exemplu. Imaginați-vă problema enumerând toate subgrupurile posibile, care pot fi formate din grupul constând din n oameni. Deoarece aceste subgrupuri pot fi de 2 „- 1 (presupunem întregul grup un subgrup, dar nu permit subgrupuri goale), orice algoritm pentru rezolvarea acestei probleme trebuie să cuprindă minimum 2“ - 1 trepte, precum și complexitatea acestuia va fi cel puțin egală cu această valoare. Dar expresia 2 „- 1, fiind exponențială, nu este limitată de nici un polinom consecință, orice soluție la această problemă prin creșterea dimensiunii grupului, din care subgrupul selectat, necesită un imens run-time ..

Spre deosebire de problema sub-grupuri, complexitatea care este mare numai din cauza mărimii de ieșire, există probleme a căror complexitate poate fi ridicată, chiar și în cazul în care rezultatul final - „nu“ este pur și simplu „da“ sau De exemplu, capacitatea de a răspunde la întrebări cu privire la veridicitatea revendicărilor care necesită adăugarea de numere reale. Putem spune cu ușurință că răspunsul la întrebarea „Este adevărat că există un număr real, care atunci când este adăugat pentru a se produce o valoare de 6?“ Este „da“, iar întrebarea, „Este adevărat că există un număr real nenul, care atunci când sunt adăugate cu ea însăși 0? „-“ nu“. Cu toate acestea, în cazul în care aceste probleme sunt din ce în ce mai complexe, capacitatea noastră de a răspunde la acestea slăbește. Dacă ne confruntăm cu o mulțime de întrebări similare, atunci probabil că doriți să utilizați un program de calculator pentru a le răspunde. Din păcate, căutarea de răspunsuri la aceste întrebări necesită timp exponențială, astfel încât computerele nu se poate menține o regularitate în a răspunde la întrebări mai dificile.

Acesta este, teoretic, rezolva problema, nu fac parte din P, au o mare complexitate timp, trebuie să recunoaștem că acestea nu pot fi rezolvate din punct de vedere practic. Oamenii de știință implicați în tehnologia de calculator, numit astfel de probleme greu de rezolvat. La rândul său, sarcinile pentru care există soluții practice, conținute în P. Prin urmare, înțelegerea frontierelor clasa P a devenit un domeniu important de studii de inginerie calculator.

Luați în considerare problema comis-voiajor, care este faptul că vânzătorul trebuie să viziteze toți clienții săi în diferite orașe, fără a depăși lungimea căii specificate, care prevede bugetul de călătorie. Sarcina sa, prin urmare, este de a găsi o cale (de la casa, prin tot orașul, și înainte de a reveni acasă), costul total al călătorie care nu depășește banii de călătorie.

Soluția tradițională la această problemă - a considerat în mod constant posibile modalități de a compara lungimea fiecare cu o limită de bani de călătorie, până când găsiți calea cea dreaptă, sau toate posibilitățile au fost epuizate. Cu toate acestea, această abordare necesită soluții nonpolynomial timp. Odată cu creșterea numărului de orașe numărul de căi care au nevoie pentru a verifica, crește mai repede decât orice polinom. În consecință, soluția problemei comis-voiajorului pentru un număr mare de orașe, în acest fel este imposibil.

Concluzionăm că, în timp rezonabil, necesită un algoritm rapid pentru rezolvarea problemei. Apetitul nostru alimentat de suspiciunea că, în cazul în care există o cale adecvată și vom selecta prima soluție va fi găsit foarte repede. În special, următoarea listă de comenzi, puteți rapid și pentru a obține cea mai bună soluție a problemei:

Luați una dintre modalitățile posibile și se calculează lungimea totală calea. în cazul în care (lungimea căii nu depășește admisibilă)

apoi (anunță succes)

altceva (nimic de declarat)

Dar acest lucru nu este un set de instrucțiuni este un algoritm în sens tehnic. Prima sa instrucțiune este ambiguă - nu indică care calea de a alege și de la care vin decizia. Aceasta se bazează pe imaginația mecanismului de program, oferind o gamă largă de soluții pentru ea. Noi spunem că o astfel de instruire nedeterminist, și se numește „algoritm“, care conține astfel de instrucțiuni, nedeterministe, algoritmul (algoritmul nedeterminist).

Vă rugăm să rețineți că o creștere a numărului de orașe de timp necesare acestei nedeterministice crește lent algoritm. Procesul de selectare a căii este pur și simplu emite o listă a orașelor, care are nevoie de timp proporțional cu numărul de orașe. In plus, timpul necesar pentru a calcula lungimea completă a căii selectate este de asemenea proporțională cu numărul de orașe, iar comparația cu calea maximă admisibilă este independent de numărul de orașe. Prin urmare, algoritmul polinomial run-time nedeterministice este limitat. Prin urmare, problema comis-voiajor poate fi rezolvată printr-un algoritm non-determinist în timp polinomial.

Desigur, soluția noastră de bază non-deterministă nu este ideal. Ea se bazează pe o selecție aleatorie. Cu toate acestea, existența sa este de ajuns pentru a sugera că, probabil, există o soluție determinist la problema comis-voiajor care se execută în timp polinomial. Adevărat sau nu - încă o întrebare deschisă. De fapt, problema comis-voiajorului - doar una dintre problemele pentru care soluțiile sunt cunoscute nedeterministice efectuate în timp polinomial, și pentru care nu au fost încă găsit o soluții deterministe polinomial timp. Teasing eficacitatea soluțiilor non-deterministă a acestor probleme ne face să sperăm că o zi va fi găsit și soluții eficiente deterministe, dar majoritatea cred că aceste probleme sunt încă mult prea complexe și dincolo de capacitatea de algoritmi deterministe eficiente.