Ma pola NP dikare bi çîna EXPTIME re wekhev be?
Pirsa ka gelo çîna NP dikare bi pola EXPTIME re wekhev be, di aliyên bingehîn ên teoriya tevliheviya hesabkerî de vedigere. Ji bo çareserkirina vê pirsê bi berfirehî, pêdivî ye ku meriv pênasîn û taybetmendiyên van çînên tevliheviyê, têkiliyên di navbera wan de, û encamên wekheviyek wusa fam bike.
Pênase û Taybetmendî
NP (Dema Polynomî ya Nedetermînîst):
Çîna NP ji pirsgirêkên biryarê pêk tê ku çareseriyek diyarkirî ji hêla makîneya Turing a diyarker ve di dema pirnomî de rast an nerast tê verast kirin. Bi awayekî fermî, zimanek (L) di NP-ê de ye ger verastkerek-dema pirnomî (V) û pirnomîlek (p) hebe ku ji bo her rêzek (x di L-yê de), sertîfîkayek (y) bi ( |y| leq p(|x|) ) û (V(x, y) = 1).
EXPTIME (Dema Hêjdar):
Di pola EXPTIME de pirsgirêkên biryarê yên ku dikarin bi makîneya Turing a diyarker di dema vekêşanê de werin çareser kirin vedihewîne. Bi awayekî fermî, zimanek (L) di EXPTIME de ye heke makîneyek Turing a diyarker (M) û domdarek (k) hebe ku ji bo her rêzek (x di L) de, (M) biryarê bide (x) di demê de (O(2 ^{n^k}) ), ku (n) dirêjahiya (x) ye.
Têkiliya Di navbera NP û EXPTIME de
Ji bo analîzkirina gelo NP dikare bi EXPTIME re wekhev be, pêdivî ye ku em têkiliyên naskirî yên di navbera van çînan de û encamên wekheviyek wusa bifikirin.
1. Vegirtin:
Tê zanîn ku NP di nav EXPTIME de ye. Ji ber ku her pirsgirêkek ku di dema pirnomîal de (wek NP) were verast kirin, dikare di wextê deqê de jî were çareser kirin. Bi taybetî, algorîtmayek pirnomî-dema nedetermînîst dikare ji hêla algorîtmayek dem-rengdêr a diyarker ve were simul kirin. Ji ber vê yekê, (nivîsa {NP} nivîsa bineteq{EXPTIME}).
2. Veqetandinî:
Baweriya berbelav di teoriya tevliheviyê de ev e ku NP bi hişkî di nav EXPTIME de ye, ango, (text{NP} nivîsa binsetneq{EXPTIME}). Ev bawerî ji vê yekê derdikeve ku pirsgirêkên NP-ê di dema pirnomîal a nedetermînîst de têne çareser kirin, ku bi gelemperî ji pirsgirêkên ku di dema vekêşana diyarker de têne çareser kirin çînek piçûktir tê hesibandin.
Encamên NP = EXPTIME
Ger NP bi EXPTIME re wekhev bûya, ew ê ji bo têgihîştina me ya tevliheviya hesabkirinê gelek encamên kûr destnîşan bike:
1. Polynomial vs.
Wekheviyek (text{NP} = nivîs{EXPTIME}) dê pêşniyar bike ku her pirsgirêkek ku di wextê nişankirî de were çareser kirin dikare di dema pirnomî de jî were piştrast kirin. Ev tê wê wateyê ku gelek pirsgirêkên ku niha têne fikirîn ku hewceyê wextê berbiçav hewce ne dikarin di şûna wê de werin verast kirin (û bi vî rengî potansiyel çareser bibin) di dema polînomî de, ku dijberî baweriyên heyî yên di teoriya tevliheviyê de ye.
2. Hilweşîna Dersên Tevliheviyê:
Ger NP bi EXPTIME re wekhev bû, ew ê di heman demê de hilweşîna çend çînên tevliheviyê jî nîşan bide. Mînakî, ev tê wê wateyê ku (text{P} = nivîs{NP}), wekî pirsgirêkên NP-temamî dê di dema pirnomî de bêne çareser kirin. Ev ê bêtir tê wê wateyê ku (text{P} = nivîs{PSPACE}), û dibe ku bibe sedema hilweşîna hiyerarşiya pirnomial.
Nimûne û Nirxên Bêtir
Ji bo ronîkirina encamên, mînakên jêrîn binêrin:
1. SAT (Pirsgirêka Têrbûnê):
SAT pirsgirêkek NP-tevahî ya naskirî ye. Ger NP bi EXPTIME re wekhev bû, ew ê tê vê wateyê ku SAT dikare di wextê vekêşana diyarker de were çareser kirin. Ya girîngtir, ew ê tê vê wateyê ku SAT dikare di dema pirnomî de were verast kirin û bi vî rengî di dema pirnomî de were çareser kirin, ku rê li ber (tekst{P} = nivîs{NP}) bigire.
2. Şah:
Pirsgirêka destnîşankirina ka lîstikvanek di pozîsyonek şetrencê de xwedî stratejiyek serketî ye, tê zanîn ku di EXPTIME de ye. Ger NP bi EXPTIME re wekhev bûya, ew ê tê vê wateyê ku pirsgirêkek weha dikare di dema polînomî de were verast kirin, ku niha nayê bawer kirin ku ne gengaz e.
Xelasî
Pirsa ka gelo pola NP dikare bi pola EXPTIME re wekhev be di teoriya tevliheviya hesabker de pirsek girîng e. Li ser bingeha zanîna heyî, tê bawer kirin ku NP bi tundî di nav EXPTIME de tête girtin. Encamên ku NP bi EXPTIME re wekhev e dê kûr be, ku bibe sedema hilweşîna çend çînên tevliheviyê û têgihîştina meya heyî ya pirnomîal li hember zemanê vekêşanê dijwar bike.
Pirs û bersivên din ên vê dawiyê di derbarê Tevlîheviyê:
- Ma pola PSPACE ne bi pola EXPSPACE re wekhev e?
- Ma pola tevliheviya P binkomek pola PSPACE ye?
- Ma em dikarin îsbat bikin ku çîna Np û P yek in bi dîtina çareseriyek polînomî ya bikêr ji bo her pirsgirêkek bêkêmasî ya NP li ser TM-ya diyarker?
- Di PSPACE de pirsgirêk hene ku ji bo wan algorîtmaya NP-ya naskirî tune?
- Ma pirsgirêkek SAT dikare bibe pirsgirêkek tevahî NP?
- Ma dibe ku pirsgirêk di pola tevliheviya NP de be heke makîneyek ziravî ya ne diyarker hebe ku dê di dema pirnomî de wê çareser bike
- NP çîna zimanên ku xwedan verastkerên dema pirnomî ne
- Ma P û NP bi rastî heman çîna tevliheviyê ne?
- Ma her çarçoveyek zimanek azad e di pola tevliheviya P de?
- Ma nakokî di navbera pênasekirina NP-ê de wekî çînek pirsgirêkên biryarê yên bi verastkerên polînomî-dem-ê re û rastiya ku pirsgirêkên di pola P-yê de verastkerên dema pirnomî jî hene?
Pir pirs û bersivan di Complexity de bibînin