
pratyaekamaina aata ooha

ganana sanklishtata siddhaantamlo, pratyaekamaina aata ooha (tarachugaa yujisi anie pilustaaru) anedi 2002loe subhash khot chesina oka ooha. "pratyaekamaina aata" anie piluvabade oka nirdishta rakam aata yokka sumaru "viluva" nuu nirnayinche samasyaku enpi-haard ganana sanklishtata undani oohistundi. idhi sthuulata yokka kaatinyam siddhaantamlo vistruta anuvartanaalanu kaligi undhi. pratyaekamaina aata ooha nijamaithe mariyu p ≤ np ayithe, aneka mukhyamaina samasyalaku bahupadi samayamlo khachitamaina parishkaram pondadam asadhyam matrame kaadu (p verses np samasya dwara pratipaadinchabadinatlugaa), conny manchi bahupadi-samaya ujjaayimpu pondadam kooda asadhyam. atuvanti ananukuulata phalitam kaligi unde samasyalalo parimitula santrupti samasyalu untaayi, ivi aneka rakaala vibhagalalo perugutaayi.
idhi nijamo kaadho anae daanipai vidya prapancham samanamga vibhajinchabadinatlu anipinchadamlo ooha asaadhaaranamainadi.
suutreekaranalu.
pratyaekamaina aata oohanu aneka samaanamaina margallo paerkonavacchu.
pratyaekamaina label cover.
pratyaekamaina aata ooha yokka krindi suutreekarana tarachugaa anchanaa yokka kaatinyamlo upayoginchabadutundi. pratyaekamaina parimitulatoe label cover" anie piluvabade eee krindi vaagdaanam samasya yokka enpi-kaatinyaanni ooha suuchistumdi. prati anchuku, rendu sheershaalapai unna rangulu konni nirdishta kramam chesina jatalaku parimitam cheyabaddaayi. "pratyaekamaina" parimitulu antey prati anchuku arder chesina jatalalo edhee oke nodku oke rangunu kaligi undavu.
dheeni ardham, "k" parimaanam yokka varnamaalapai pratyaekamaina parimitulatoe label cover yokka udaaharananu π "e": ["k"] → ["k"] kramaparivartanala sekaranato kalisi nirdesinchina graphga suuchimchavachchu, graph yokka prati anchu "e" kii okati. oka label cover udaaharanaku ketayinchinadi "g" yokka prati sheershaaniki ["k"] = {1,2, loe viluvanu istundi... k}, tarachugaa "rangulu" anie pilustaaru."
atuvanti sandarbhaalu oka sheersham yokka rangu daani poruguvaari rangulanu pratyaekamgaa nirvachistundi, anduvalla daani mottam anusandhaaninchabadina bhaagaaniki anae ardhamlo balamgaa parimitam cheyabaddaayi. anduvalla, input udaaharana chellubaatu ayye assainmentnu angeekaristhe, atuvanti assainmentnu oke node yokka anni rangulapai punaraavrutam cheyadam dwara samarthavantamgaa kanugonavacchu. mukhyamgaa, icchina udaaharana santruptikaramaina panini angeekaristundaa anie nirnayinche samasyanu bahupadi samayamlo parishkarinchavacchu.
pratyaekamaina label cover udaaharana yokka "viluva" anedi edainaa ketayimpu dwara santrupti chendagala parimitula yokka bhinnam. santruptikaramaina sandarbhaallo, eee viluva 1 mariyu kanugonadam sulabham. marovaipu, asantruptikaramaina aata yokka viluvanu nirnayinchadam chaalaa kashtamgaa anipistundi, dadapuga kooda. pratyaekamaina aata ooha eee kashtanni lanchanaprayamga chestundi.
marinta adhikarikamga, pratyaekamaina parimitulatoe kuudina ("sii", "luu")-gyap label-cover samasya krindi vaagdaanam samasya ("ell" avunu ", ell" ledhu):
ikkada "g" anedi pratyaekamaina parimitulatoe label cover samasyaku oka udaaharana.
pratyaekamaina aata ooha prakaram, taginanta chinna jatha sthiraamkaalaku "ε", "δ"> 0, sthiraamkam "k" undhi, antey (1 − "δ", "ε")-gyap label-cover samasya, parimaanam "k" varnamaalapai pratyeka parimitulatoe np-haard.
graphlaku badulugaa, label cover samasyanu leanier sameekaranaala paramgaa roopondinchavacchu. udaaharanaku, manaku puurnaamkaala maadyulo 7 paie sarala sameekaranaala vyavastha undani anukundam
idhi pratyaekamaina parimitulatoe kuudina label cover samasyaku oka udaaharana. udaaharanaku, modati sameekaranam prastaarana (1,2) kuu anugunamgaa untundi, ikkada (1,2) ("x" 1) = 2 "x" 2 maadyulo 7.
rendu-prover proof systems.
oka pratyaekamaina aata anedi "rendu-prover vann-round (2p1r) game" yokka pratyeka kesu. rendu-prover oka-round aatalo iddaru aatagaallu (proverse anie kooda pilustaaru) mariyu oka referee untaaru. referee prati aatagaadiki telisina sambhaavyata pampinhee nundi teesukunna prasnanu pamputaadu, mariyu prati aatagadu samadhanam pampali. samadhanalu sthira parimaanam nundi vastaayi. aatagallaku pampina prasnalu mariyu vaaru andinchina samadhaanaalapai aadharapadi unde oka anchanaa dwara aata perkonabadutundi.
aata samayamlo okaritho okaru sambhashinchalenappatiki, aatagaallu mundugaane oka vyuuhaanni nirnayinchukovacchu. vaari prasnalu mariyu vaari samaadhaanaalato anchanaa santrupti chendinatlayithe aatagaallu gelustaaru.
modati aatagadi prati prasnaku mariyu prati samaadhaanaaniki, rendava aatagadi dwara sarigga oka samadhanam unte, adhi aatagallaku vijayaniki daariteesthe, rendu-prover vann-round aatanu "pratyaekamaina aata" anie pilustaaru. aata yokka "viluva" anedi anni vyuuhaalapai aatagallaku garishta gelupu sambhaavyata.
pratyaekamaina aata ooha prakaram, prati taginanta chinna jatha sthiraamkaalu "ε", "δ"> 0, oka sthiramaina "k" undhi, antey eee krindi vaagdaanam samasya ("l" avunu, l "ledhu) np-haard
ikkada "g" anedi oka pratyaekamaina aata, dheeni samadhanalu "k" parimaanam nundi vastaayi.
sambhaavyamgaa tanikhi cheyagala rujuvulu.
pratyamnaayamgaa, pratyaekamaina aata ooha enpeelo samasyalaku oka nirdishta rakam sambhaavya tanikhi cheyadagina rujuvu unikini suuchistumdi.
oka pratyaekamaina aatanu prasna sanklishtata 2 thoo pratyaekamaina anukuulinchani sambhaavyatatoo tanikhi cheyagala rujuvugaa chudavachu, ikkada dhruvikarana yokka prati jatha saadhyamayye prasnalaku mariyu modati prasnaku prati saadhyamaina samaadhaanaaniki, dhruvikaranakartanu angeekarinchelaa chese rendava prasnaku khachitamgaa oka saadhyamaina samadhanam untundi, mariyu dheeniki viruddhamgaa untundi.
pratyaekamaina aata ooha prakaram, taginanta chinna jatha sthiraanka suutram _ 2 kii sthiramaina suutram _ 3 untundi, antey np looni prati samasyaku parimaana suutram _ 3 yokka varnamaalapai sampoorna suutram _ 5, dhwani suutram _ 6, mariyu yaadruchchika sanklishtata suutram _ 7 thoo sambhaavyamgaa tanikhi cheyadagina rujuvu untundi, idhi oka pratyaekamaina aata.
auchityam.
2002loe subash khot dwara eee pratyaekamaina aata oohanu pravesapettaaru, dheeni dwara sthuulata yokka kaatinyam siddhaantamlo konni prasnalapai purogati saadhinchavachchu.
pratyaekamaina aata ooha yokka nijam aneka telisina ujjaayimpu algorithamla yokka optimalityni suuchistumdi (p ≤np anie oohinchadam). udaaharanaku, graphlo garishta kothanu anchanaa vaeyadaaniki goemans mariyu villiamson yokka algorithm dwara saadhinchina ujjaayimpu nishpatti pratyaekamaina aata ooha mariyu p ≤ np nuu oohinchi edainaa sankalana sthiraamkam lopala uttamamainadi.
pratyaekamaina aata ooha suuchistumdani telisina phalitaala jabita prakkane unna pattikalo choopabadindi, dheenitho paatu balaheenamaina ooha p ≤ np kii sambandhinchina uttama phalitaalu untaayi. suutram _ 8 ledhaa suutram _ 9 yokka sthiraamkam antey phalitam prati "sthiraamkam" (samasya parimaanaaniki sambandhinchi) suutram _ 10 kante khachitamgaa ekkuva ledhaa takkuva untundi.
charcha mariyu pratyaamnaayaalu.
prastutam, pratyaekamaina aata ooha yokka satyaaniki sambandhinchi ekaabhipraayam ledhu. ooha yokka konni balamaina roopaalu niroopinchabadaledu.
oka pratyaekamaina aata yokka viluva kaneesam suutram _ 5 ayinappudu kesunu vaeru chese ooha yokka vaerae roopam, viluva chaalaa suutram _ 6 vadda unnappudu bahupadi-samaya algorithamlaku asadhyam (conny bahusha np-haard kaadu). ooha yokka eee roopam ippatikee sthuulata yokka kaatinyamlo anuvartanaalaku upayogakaramgaa untundi.
p = np tappa, ooha yokka paina perkonna suutreekaranalaloo sthiramaina suutram _ 13 avasaram. pratyekata avasaranni tolaginchinatlayithe, sambandhita prakatana samaantara punaraavruta siddhaantam dwara nijamani telustundi, 
marek karpinsky mariyu warren shoody pratyaekamaina aata samasya yokka dattamaina sandarbhaala kosam sarala samaya anchanaa pathakaalanu nirminchaaru.
2008loe, prasad raghavendra pratyaekamaina aata ooha nijamaithe, prati addanki santrupti samasyaku uttama ujjaayimpu nishpatti oka nirdishta saadhaarana semifinite prograaming udaaharana dwara ivvabadutundi, idhi pratyaekamaina bahupadi.
2010loe, prasad raghavendra mariyu david steerer "gyap-small-sett vistarana" samasyanu nirvachinchaaru, mariyu idhi enpi-haard anie oohinchaaru. eee ooha pratyaekamaina aata oohanu suuchistumdi. puurti dwaipaakshika upagraflanu kanugonadaaniki ujjaayimpu phalitaala yokka balamaina kaatinyaanni niroopinchadaaniki kooda idhi upayoginchabadindi.
2010loe, sanjeev arora, bowaz barak mariyu david steerer pratyaekamaina aata samasya kosam upa-ghaataanka samaya anchanaa algorithamnu kanugonnaru.
2012loe, chaalaa varaku suutram _ 14 viluvatho unna sandarbhaalanu kaneesam suutram _ 15 viluvatho unna sandarbhaala nundi vaeru cheyadam np-haard anie choopabadindi.
2018loe, varusa patraala taruvaata, 2-2 aatala ooha anie piluvabade ooha yokka balaheenamaina samskarana niroopinchabadindi. oka nirdishta konamlo, idhi asalu oohalo "sagam" anie rujuvu chestundi. idhi pratyaekamaina label cover kosam baga telisina antaraanni kooda meruguparustundih chaalaa suutram vadda viluvatho unna sandarbhaalanu kaneesam suutram 15 viluvatho unna sandarbhaala nundi vaeru cheyadam np-haard.