Konplexutasun konputazionalaren teoria

Konplexutasun konputazionalaren teoria edo konplexutasun informatikoaren teoria teoria konputazionalaren adar bat da, arazo konputazionalak berezko zailtasunaren arabera sailkatzean eta konplexutasun klase horien arteko erlazioan oinarritzen dena.

Arazo bat berez zaila gisa sailkatzen da, bere konponbideak baliabide konputazional kopuru handia eskatzen badu, erabilitako algoritmoa edozein dela ere. Konplexutasun konputazionalaren teoriak baieztapen hori formalizatzen du arazo horiek aztertzeko eta haiek ebazteko behar diren baliabideen kopuruaren kuantifikaziorako eredu konputazional matematikoak sartuz, hala nola denbora eta memoria.

Konplexutasun konputazionalaren teoriaren helburuetako bat ordenagailuan egin daitekeenaren eta egin ezin denaren muga praktikoak zehaztea da. Konplexutasun konputazionalaren teoriarekin lotutako beste alor batzuk algoritmoen analisia eta konputagarritasunaren teoria dira. Algoritmoen analisiaren eta konplexutasun konputazionalaren teoriaren arteko alde nabarmena da lehena algoritmo jakin batek arazo bat ebazteko behar duen baliabide kopurua zehazteaz arduratzen da, eta, bigarrena, berriz, arazo bera ebazteko erabil litezkeen algoritmo posible guztiak aztertzen ditu.

Konplexutasun konputazionalaren teoria baliabide kopuru jakin batekin ebatzi daitezkeen edo ezin diren arazoak sailkatzen saiatzen da. Era berean, baliabide horiei, murrizketak ezartzea da konputagarritasunaren teoriatik bereizten duena, hau da, zer-nolako arazok ebatzi daitezkeen algoritmikoki.

Historia

Algoritmoen konplexutasunaren inguruan ikerketa egin aurretik, teoria horren oinarriak ezarri zituzten hainbat ikertzailek. Ekarpenik eragingarrienetako bat Turing makinen definizioa izan zen, 1936an, ordenagailuaren nozio oso malgu eta sendoa izan zena. 1940ko eta 1950eko hamarkadetan ordenagailuak garatu zirenez, Turing-makina konputazio eredu teoriko zuzena zela frogatu zen.

Hala ere, azkar aurkitu zen Turing makinaren oinarrizko ereduak ez zuela ordenagailu batek behar zuen denbora eta memoria kuantifikatzen, arazo larria gaur egun, eta are gehiago orduan. Denbora eta espazioa sarrerako luzeraren arabera neurtzeko ideia 1960ko hamarkadaren hasieran sortu zen Hartmanis eta Stearns-en bidez, eta, beraz, konplexutasun konputazionalaren teoria sortu zen.

Hasieran, ikertzaileak konplexutasunaren neurri berriak ulertzen (eta nola erlazionatzen ziren elkarren artean) saiatzen ziren. 1965ean, Edmondsek algoritmo on gisa definitu zuen polinomio batez mugatuta dagoen exekuzio-denbora, hau da, exekuzio-denbora polinomikoa duena. Horrek, konplexutasun konputazionalaren teorian, kontzeptu garrantzitsuenetako bat sortu zuen: NP-osotasuna, eta bere oinarrizko galdera da ea P = NP den.

Eremua loratzen hasi zen, Stephen Cook ikertzaile estatubatuarrak eta Leonid Levin ikertzaile sobietarrak, modu independentean lan eginez, frogatu zutenean NP-osoak diren arazo garrantzitsuak existitzen zirela. 1972an, Richard Karpek ideia hori urrats bat gehiagora eman zuen, eta 21 konbinazio eta grafo-teorikoak diren arazoak (konputazionalki konpongaitzak zirela ezaugarritutakoak) NP-osoak zirela erakutsiz. 1970eko hamarkadan ere, konplexutasun-klaseen hazkundea izan zen, ikertzaileak zeuden eredu konputazional desberdinak ulertzen saiatzen ziren heinean.

1980ko hamarkadan, eredu finituen gorakada izan zen, prozesu konputazionala, berez, beste modu batean aztertzen zutenak. P = NP bezalako arazoen ikuspegi berri bat sortu zen, eta nahiz eta eredu horiek konplexutasun-klaseak bereiziz euren mugak izan, ikuspegi horrek eredu horien mugak hobeto ulertzeko teknika konbinatzaileak sortu zituen.

Dagoeneko 90eko hamarkadan, konputagailu kuantikoen moduko konputazio-eredu berriak ikertu ziren, non zeregin berak konplexutasun desberdina izan dezaken konputazio klasikoan eta konputazio kuantikoan. Hala ere, hainbat muga daude, horien artean, eredu horretarako hardwarea garatzearena eta kalkuluak egiteko espazio kopuru handia behar dela.

Arazoak, algoritmoak eta konplexutasuna

Arazoak berez konpongaitzak eta zailtasun baliokideak diren arazoei erreferentzia egiteko, beharrezkoa da oinarrizko termino batzuk ulertzea.

Arazo konputazionala

Arazo konputazional batek erantzun beharreko galdera bat da, oro har, hainbat parametro edo aldagai libre dituena, zeinen balioak zehaztu ez diren. Arazo bat honela deskribatzen da:

1. Bere parametro guztien ikuspegi orokorra (sarrera edo irteera izan daiteke).
2. Erantzunak edo soluzioak bete behar dituen propietateak deskribatzen dituen adierazpena.

arazo baten instantzia arazoaren parametro guztietarako balio partikularrak zehazten direnean lortzen da. Adibidez, har dezagun kontuan lehentasun probaren arazoa. Instantzia zenbaki bat da (adib. 15) eta irtenbidea bai da zenbaki lehena bada, eta ez bestela. Beste modu batean ikusita, instantzia arazoaren sarrera jakin bat da, eta irtenbidea emandako sarrerari dagokion irteera da.

Erabaki arazoak

Erabaki-arazo bat konputazio-arazo mota berezi bat da, eta erantzuna bai edo ez baino ez da (edo, formalki, 1 edo 0).

Erabaki-arazo bat hizkuntza formal gisa ikus liteke, non hizkuntzari dagozkion elementuak bai erantzunaren arazoaren instantziak diren eta hizkuntzari ez dagozkionak, berriz, ez erantzuna duten instantziak diren. Helburua da erabakitzea (algoritmo baten laguntzaz) sarrera bat kontuan hartutako hizkuntza formalaren elementu bat den. Algoritmoak bai itzultzen badu, algoritmoak sarrera onartzen duela esaten da; bestela, baztertzen duela esaten da.

Erabaki-arazoak konplexutasun konputazionalaren teoriaren azterketa-objektu nagusietako bat dira, bada, NP-osotasuna zuzenean aplikatzen zaie arazo mota horiei optimizazio-problemei ordez. Arazo horiek garrantzi handia dute, zeren ia edozein arazo erabaki arazo bihurtu baitaiteke.

Algoritmoak

Artikulu nagusia: «Algoritmo»

Informalki, algoritmoak arazoak ebazteko urratsez urratseko prozedurak direla esan dezakegu. Ordenagailu-programa soil gisa pentsa liteke, hizkuntza artifizial zehatz batean idatziak

Algoritmo batek A arazo bat ebazten duela esaten da, baldin eta algoritmoa A-ren I den edozein instantziari aplika dakioken eta instantzia horri beti soluzioa emango diola ziurtatzen bada. Oro har, arazo jakin bat konpontzeko algoritmorik eraginkorrena aurkitzea interesatzen zaigu. Bere zentzurik zabalenean, eraginkortasunaren nozioak algoritmo bat exekutatzeko beharrezkoak diren baliabide konputazional guztiak biltzen ditu.

Algoritmo eraginkorrena, normalean, azkarrena esan nahi dugu. Algoritmo bat praktikan erabilgarria izateko (nahikoa eraginkorra den ala ez zehazteko garaian denbora-eskakizunak faktore nagusi izan ohi direnez) baliabide horretan zentratuko gara.

Denbora polinomikoko algoritmoak eta arazo konpongaitzak

Informatikariek denbora polinomikoko algoritmoen eta denbora esponentzialeko algoritmoen arteko bereizketa egiten dute algoritmoak «nahikoa eraginkorra» eta «oso eraginkorra» gisa ezaugarritzeko orduan, hurrenez hurren.

Denbora polinomialeko algoritmoa definitzen da goiko muga asintotiko O (p(n)) baten barruan (batzuetan ordena deitua) denbora- eta konplexutasun-funtzioa duen bezala p funtzio polinomiko baterako, non n sarreraren tamaina adierazten duen. $O(e^{n}),$ denbora esponentzialeko algoritmoak dira algoritmoarekin egin beharreko ziklo-kopurua $e^{n}$ funtzioarekiko proportzoinala dena; hau da, algoritmoa exekutatzeko behar den konputazio-potentzia esponentzialki hazten da arazoaren $n$ neurriraino.

Denbora esponentzialeko algoritmo gehienak bilaketa zehatz baten aldakuntza sinpleak dira, eta denbora polinomikoko algoritmoak arazoren egitura sakonago baten bidez lortzen dira, normalean. Konplexutasun konputazionalaren teorian, adostasun bat dago arazo bat ez dela ondo ebazten denbora polinomikoko algoritmo batek ebazten duen arte. Beraz, arazo bat konponezintzat joko dugu, baldin eta hain zaila bada ez dagoela denbora polinomikoko algoritmorik ebazteko gai

Konplexutasun klaseak

Konplexutasun-klasea konplexutasun konputazional bera duten arazo multzoa da.

Konplexutasun-klaseak zehazten

Konplexutasun-klase sinpleenak, faktoreak kontuan hartuta, honela definitzen dira:

• Konputazio-arazo mota: Gehien erabiltzen diren arazoak erabaki-arazoak dira, baina konplexutasun-klaseak definitu daitezke beste arazo mota batzuetarako.
• Konputazio-eredua: Konputazio eredurik ohikoena Turing-makina determinista da, baina konplexutasun-klase asko Turing-makina ez-deterministetan, Turing-makina kuantikotan, etab.
• Mugatuta dagoen baliabidea(k) eta muga(k): Bi ezaugarri horiek elkarrekin erabiltzen dira normalean, adibidez, denbora polinomikoa, espazio logaritmikoa, sakontasun konstantea, etab.

Turing-makina deterministak eta P klasea

P klaseak Turing-makina determinista batek denbora polinomikoan ebazten dituen arazoak biltzen ditu.

Aurreko definiziorako, konputazio-eredua ezarri da: Turing-makina determinista. Turing-makinaren aldaera desberdinak daude, eta jakina da horietako ahulenek, izan ere, indartsuena simula dezaketela denbora polinomiko bat gehituz, gehienez. Church-Turing Tesiaren ondorengo hamarkadetan, beste eredu konputazional batzuk sortu ziren, eta frogatu zen Turing-makinak ere simula zezakeela gehienez denbora polinomiko bat ere gehituz. Beraz, eredu horietarako P-ren antzekoa dena, ez da Turing-makinaren konputazio-ereduaren P klasea baino handiagoa.

P klaseak zeregin garrantzitsua betetzen du konplexutasun konputazionalaren teorian, zeren eta:

1. P aldaezina da Turing-makina deterministaren polinomikoki baliokideak diren konputazio-eredu guztientzat.
2. Gutxi gorabehera, P ordenagailuan modu errealistan konpon daitezkeen arazoen klaseari dagokio.

Konputazio ez-determinista eta NP klasea

Askotan, arazoetan indar gordina erabiltzea saihestu dezakegu denbora polinomikoan soluzioak lortzeko. Hala ere, arazo batzuetarako, ez da hori lortu; hau da, ez dago denbora polinomikoan ebazten dituen algoritmorik ezagutzen. Agian, arazo horiek oraindik ezezagunak diren printzipioetan oinarritzen diren denbora polinomikoko algoritmoak dituzte, edo, agian, arazo horiek ezin dira denbora polinomikoan konpondu, berez zailak direlako.

NP konplexutasun-klasea denbora polinomikoko arazo egiaztagarriak osatzen dute. Egiaztagarria den arazoz esan nahi dugu, horrelako soluzio-ziurtagiri bat emanda (konponbide-hautagaia), egiazta daitekeela ziurtagiria zuzena dela sarreraren tamainako denbora polinomikoan. NP klaseko arazoei NP arazoa deitzen zaie normalean.

NP terminoa denbora polinomikoan ez deterministatik dator, eta klase horren karakterizazio alternatibo batetik eratorria da, non Turing-makina ez deterministak erabiltzen diren. Informalki, NP klasea algoritmo ez-determinista baten arabera defini daiteke (gogoratu algoritmoaren eta Turing-makinaren arteko baliokidetasuna).

Aipatutako algoritmoa 2 fasez osatuta dago. I arazoaren adibide bat emanda, lehenengo faseak S soluzio hautagai bat asmatu besterik ez du egiten. Ondoren, egiaztapen-etapak I eta S jasotzen ditu sarrera gisa, eta kalkulua modu deterministan egiten hasten da, azkenean, bai erantzunarekin edo ez erantzunarekin geldituz, edo zenbatzen jarraitzen du gelditu gabe.

P klasea bezala, NP klasea ez da kalkulu-eredu ez-determinista aukeratzeko gai, eredu horiek polinomikoki baliokideak baitira.

Konplexutasun klase garrantzitsuak

Konplexutasun-klase garrantzitsu asko defini daitezke algoritmoak erabiltzen duen denbora edo espazioa mugatuz. Erabaki-arazo mota horietako batzuk hauek dira:

Konplexutasun klasea	informatika-eredua	baliabideen murrizketa
DTIME (f (n))	Turing-makina determinista	Eguraldia f (n)
P	Turing-makina determinista	Denbora poli(n)
PP	Turing-makina ez-determinista	Denbora poli(n)
EXPTIME	Turing-makina determinista	Denbora 2 poli(n)
NTIME ( f (n))	Turing-makina ez-determinista	Eguraldia f (n)
NP	Turing-makina ez-determinista	Denbora poli(n)
NEXPTIME	Turing-makina ez-determinista	Denbora 2 poli(n)
DSPACE ( f (n))	Turing-makina determinista	Espazioa f (n)
L	Turing-makina determinista	Zuriunea O (log n )
PSPACE	Turing-makina determinista	espazio poli(n)
ESPAZIOA	Turing-makina determinista	Zuriunea 2 poli(n)
NESPAZIOA ( f (n))	Turing-makina ez-determinista	Espazioa f (n)
NL	Turing-makina ez-determinista	Zuriunea O (log n )
NPSPACE	Turing-makina ez-determinista	espazio poli(n)
NEXPSPACE	Turing-makina ez-determinista	Zuriunea 2 poli(n)

P = NP galdera

Artikulu nagusia: «P vs NP problema»

P eta NP klaseen arteko erlazioa oinarrizkoa da NP-osotasunaren teoriarako. Intuitiboki, P, izan ere, NPren azpimultzo bat dela uste dugu. Eta, hala, denbora polinomio-denbora deterministako algoritmo baten bidez ebatzitako erabaki-arazo oro ere ebatzi daiteke denbora polinomiko algoritmo ez-determinista baten bidez. Besterik gabe, kontuan izan behar da edozein algoritmo determinista erabil daitekeela algoritmo ez-determinista baten egiaztapen-etapan. B baldin bada P-ren arazo bat eta A polinomio-denborazko algoritmoa baldin bada B-rentzat, orduan, polinomio-denbora algoritmo ez determinista bat eraiki daiteke B-rentzat A egiaztapen etapan soilik erabiliz eta asmatze-etapa alde batera utzita. Beraz, B baldin badagokio P-ri, B ere NPri dagokio.

Informatikaren alorrean, P = NP galdera garrantzitsuenetakoa da, konponbide bat aurkituz gero izango lukeen oihartzun handia dela eta. P = NP bada, polinomikoki egiazta daitekeen edozein arazo polinomikoki erabakigarria izango litzateke. Ikertzaile gehienek uste dute klase horiek ez direla berdinak, NP arazo ezberdinetarako denbora polinomikoko algoritmoak aurkitzeko ahalegin handi bat egin delako. Ikertzaileak saiatu ere dira frogatzen klaseak desberdinak direla, baina horrek indar gordinaren bilaketa ordezkatzeko algoritmo eraginkorrik ez dagoela erakustera eramango luke.

NP-osotasuna

Murrizketa polinomikoa

Murrizketa, izan ere, arazo bat beste arazo batean bihurtzea da. Intuitiboki, Q arazo bat beste Q' arazo izatera murriztu daiteke Q arazoaren edozein instantzia erraz adierazten bada eta Q' arazoaren instantzia gisa eta haren ebazpenak Q-ren instantziari irtenbidea ematen badio.

Murrizketa mota asko daude murrizketa metodoan oinarritutakoak, hala nola Cook-en murrizketak, Karp-en murrizketak, Levin-en murrizketak eta konplexutasun-loturan oinarritutakoak, hala nola polinomio-denbora murrizketa edo espazioaren murrizketa logaritmikoa. Gehien erabiltzen den murrizketa polinomiko-denborazko murrizketa da; hau da, murrizketa-prozesuak denbora polinomikoa hartzen duela adierazten du.

NP-osoen arazoak

Denbora polinomikoaren murrizketek, modu formalean, arazo bat, gutxienez, beste bat bezain zaila dela frogatzeko elementuak eskaintzen dizkigu, faktore polinomiko bateko aldearekin. Horiek, ulertzen laguntzeaz gain, ezinbestekoak dira NP-osoen arazoak definitzeko..

NP-osoen arazo klaseak NP-ren arazorik zailenak ditu, P-ren egotetik urrunen dauden zentzuan. P = NP arazoa ebatzi ez denez, B arazo bat A arazo batera murriztea A-rentzat denbora polinomikoko soluziorik ezagutzen ez dela adieraziko luke. Hori da A-rentzako denborazko soluzio polinomiko batek B-rentzako soluzio polinomiko baten existentzia adieraziko lukeelako. Era berean, NP arazo guztiak multzo honetara murriztu daitezkeenez, NP-osoa den arazo bat denbora polinomikoan ebatzi daitekeena aurkitzea P = NP dela esan nahiko luke.

NP-osotasunaren garrantzia

Beharbada, P desberdina dela NP-tik ustearen informatikarien arrazoirik sinesgarriena NP-osoa arazo klasearen existentzia da. Klase horrek propietate bitxia du: NP-osoko edozein arazo denbora polinomikoan ebatzi badaiteke, orduan, NP-ren arazo bakoitzak denbora polinomikoko soluzioa du; hau da, P = NP. urtetan aztertu arren, ez da denbora polinomikoko algoritmorik aurkitu NP-osoa den edozein arazotarako.

Ikuspuntu teorikotik, ikertzaile batek P klasea NP klasetik ezberdina dela erakutsi nahian, NP osoko arazo batean zentratu liteke. NP-ren edozein arazok denbora polinomikoa baino gehiago behar badu, orduan, NP-osoa ere bada. Gainera, P = NP dela frogatzen saiatzen den ikertzaile batek denbora polinomikoko algoritmo bat besterik ez du aurkitu behar NP-osoa den arazorako.

Ikuspegi praktikotik, NP-osotasun fenomenoak denbora galtzea ekidin dezake arazo jakin bat ebazteko existitzen ez den denbora polinomiko-algoritmo bat bilatzean. Arazo jakin bat denbora polinomikoan ebatzi ezin daitekeela frogatzeko elementu matematikorik ez badugu ere, uste dugu P ez dela NP-ren berdina; beraz, arazoa NP-osoa dela frogatzea froga sendoa da ez dela polinomikoa.

NP arazoei aurre eginez

Arazo konponezinaren definizioa kontuan hartuta, P = NP betetzen ez bada, NP-osoko arazoak konponezinak dira.

Praktikan, arazo asko NP-osoak dira, eta oso garrantzitsuak dira amore emateko, besterik gabe, ez dakigulako nola aurkitu soluzio optimoa denbora polinomikoan. Arazo bat NP-osoa bada ere, itxaropena egon daiteke. NP-osoa den arazo bati aurre egiteko oinarrizko hiru estrategia daude:

• Sarrera txikia bada, exekuzio denbora esponentziala duen algoritmoa guztiz onargarria izan daiteke.

• Denbora polinomikoan ebatzi daitezkeen kasu berezi batzuk isolatu litezke.

• Hurbilketak erabil genitzake denbora polinomikoan optimotik nahiko hurbil dauden soluzioak aurkitzeko. Praktikan, onargarria da optimotik hurbil dauden soluzioak lortzea. Algoritmo horiei hurbilketa algoritmo deitzen zaie, eta, kasu askotan, heuristikan eta metaheuristikan oinarritzen dira .

Bibliografia

• Cook, Stephen. (1983). «An overview of computational complexity» Commun. ACM (ACM) 26 (6): 400–408. ISSN 0001-0782..
• Fortnow, Lance; Homer, Steven. (2002). «A Short History of Computational Complexity» Bulletin of the EATCS 80: 95–133..
• Arora, Sanjeev; Barak, Boaz. (2009). Computational Complexity: A Modern Approach. Cambridge ISBN 978-0-521-42426-4..
• Sipser, Michael. (2006). Introduction to the Theory of Computation. (2da. argitaraldia) Thomson Course Technology ISBN 0-534-95097-3..
• Garey, Michael R .; Johnson, David S., (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5 .
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. (2010). Introduction to Algorithms. (3ra. argitaraldia) MIT Press and McGraw-Hill ISBN 0-262-03384-4...

Ikus, gainera

• P eta NP konplexutasun klaseak

Kanpo estekak

• Datuak: Q205084
• Multimedia: Computational complexity theory / Q205084