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
Pirsa "Gelo pirsgirêkek di pola tevliheviya NP de hebe heke makîneyek Turing a ne diyarker hebe ku dê di dema pirnomî de wê çareser bike?" di teoriya tevliheviya hesabî de têgehên bingehîn disekine. Ji bo ku em bi berfirehî vê pirsê çareser bikin, divê em pênasîn û taybetmendiyên çîna tevliheviya NP û rola makîneyên Turing ên ne-determînîst (NDTM) binirxînin.
Pênaseya NP
Çîna NP (dema pirnomî ya ne diyarker) ji pirsgirêkên biryarê pêk tê ku çareseriyek diyarkirî ji hêla makîneya Turing a diyarker (DTM) ve dikare di dema pirnomî de rast an nerast were verast kirin. Bi fermî, pirsgirêkek biryarê di NP-ê de ye heke algorîtmayek verastkirina-dema polînomî hebe ku dikare rastbûna sertîfîkayek (an şahidiyek) ji bo mînakek pirsgirêkê verast bike.
Makîneyên Turingê yên Ne Determînîst
Makîneya Turing a ne-determînîst modelek teorîkî ya hesabkirinê ye ku kapasîteyên makîneyek Turing a diyarker berfireh dike. Berevajî DTM, ku rêyek yekjimarî ya ku ji hêla fonksiyona veguheztina wê ve hatî destnîşan kirin dişopîne, NDTM dikare bi hevdemî gelek rêyên hesabkirinê bişopîne. Di her gavê de, NDTM dikare ji komek veguheztinên gengaz "hilbijêre", bi bandor gelek hesabên mimkun bi paralelî vekole.
Çareserbûna Polynomial-Time ji hêla NDTMs
Pirsgirêk tê gotin ku ji hêla NDTM-ê ve di dema pirnomî de çareser dibe heke algorîtmayek ne-determînîst hebe ku dikare di nav çend gavan de çareseriyek ji pirsgirêkê re bibîne ku di mezinahiya têketinê de pirnomî ye. Ev tê vê wateyê ku ji bo her mînakek pirsgirêkê, NDTM dikare rêyek hesabkerî ku di dema polînomî de rê li çareseriyê vedike vekole.
Têkiliya Di navbera NP û NDTMs de
Çîna NP dikare di çarçoveya NDTM-an de wekhev were destnîşankirin. Bi taybetî, pirsgirêkek biryarê di NP de ye ger û tenê heke NDTM hebe ku dikare pirsgirêkê di dema polînomî de çareser bike. Ev wekhevî ji vê yekê derdikeve ku NDTM dikare sertîfîkayek ne-determinîst texmîn bike û dûv re wê di dema polînomî de bi determînîst verast bike.
Ji bo ronîkirina vê yekê bi mînakek, pirsgirêka naskirî ya NP-tevahî, pirsgirêka têrbûna Boolean (SAT) binirxînin. Di forma normal a hevedudanî (CNF) de formula Boolean tê dayîn, peywir ev e ku meriv diyar bike ka ji guhêrbarên ku formulê rast dike veqetandinek nirxên rastiyê heye yan na. NDTM dikare SAT-ê di dema polînomî de bi texmînkirina ne-determinîstîkî veqetandek nirxên rastiyê çareser bike û dûv re jî bi awakî diyarker kontrol bike ka peywir formulê têr dike. Pêngava verastkirinê, ku tê de nirxandina formula di bin peywira texmînkirî de ye, dikare di dema pirnomî de were kirin.
Encamên Çareserkirina Polynomial-Time ji hêla NDTMs
Li gorî pênaseyên jorîn û hevberdana di navbera NP û çareserbûna dema pirnomî ya ji hêla NDTM-yan ve, em dikarin encam bidin ku heke NDTM hebe ku pirsgirêkek di dema pirnomî de çareser bike, wê hingê pirsgirêk bi rastî di NP de ye. Ev ji ber ku hebûna NDTM-ya wusa tê vê wateyê ku ji bo pirsgirêkê algorîtmayek verastkirina-dema polînomî heye. Qonaxa texmînkirina ne-determînîst a NDTM bi hilberîna sertîfîkayekê re têkildar e, û qonaxa verastkirina diyarker bi algorîtmaya verastkirina polînomî-dem re têkildar e.
Nirx û Nimûneyên Bêtir
Ji bo ronîkirina vê têgehê, bila em mînakên din ên pirsgirêkên di NP û têkiliya wan bi NDTM-an re bifikirin:
1. Pirsgirêka Rêya Hamiltonian: Ji ber ku grafiyek tê dayîn, pirsgirêka Rêya Hamiltonî dipirse gelo rêyek heye ku tam carekê seredana her verteksê bike. NDTM dikare vê pirsgirêkê di dema polînomî de çareser bike bi texmînkirina ne-determînîst rêzek risteyan û dûv re verast bike ka rêzik rêyek Hamiltonî ya derbasdar pêk tîne. Pêvajoya verastkirinê kontrolkirina cîrantiya lûtkeyên li pey hev vedihewîne û piştrast dike ku her vertek tam carekê tê serdan, ku her du jî dikarin di dema pirnomî de bêne kirin.
2. Pirsgirêka Binkomê: Ji bo komek ji hejmarên bêkêmasî û berhevokek armanc tê dayîn, pirsgirêka Binkomek Sum dipirse gelo binkeyek ji hejmarên bêkêmasî hene ku bi mebestê berhev dike. NDTM dikare vê pirsgirêkê di dema polînomî de çareser bike bi ne-determînîstî texmînkirina binekomek jimareyan û dûv re verast bike ka berhevoka binkomê bi armancê re ye. Pêngava verastkirinê bi berhevkirina hêmanên binkoma texmînkirî, ku dikare di dema pirnomî de were kirin, vedihewîne.
3. Pirsgirêka Rengkirina Grafikê: Ji ber ku grafek û hejmarek reng têne dayîn, pirsgirêka Rengdêrkirina Grafê dipirse gelo gengaz e ku rengdêrên grafîkê wisa werin reng kirin ku tu du xalên cîran yek reng parve nekin. NDTM dikare vê pirsgirêkê di dema polînomî de çareser bike bi ne-determînîstî rengan li risteyan veqetîne û dûv re verast bike ka rengdêr derbasdar e. Pêngava verastkirinê kontrolkirina rengên lûtkeyên cîran, ku dikare di dema polînomî de were kirin, vedihewîne.
Xelasî
Di ronahiya pênase û mînakên pêşkêşkirî de, diyar e ku pirsgirêk bi rastî dikare di çîna tevliheviya NP de be heke makîneyek Turing a ne-determînîst hebe ku dê di dema pirnomî de wê çareser bike. Ev têkilî bingehek ji teoriya tevliheviya hesabkerî ye û wekheviya di navbera çareserbûna-dema polînomî de ji hêla NDTMs û endametiya di pola NP de destnîşan dike.
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?
- Ma pola NP dikare bi çîna EXPTIME re wekhev be?
- 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?
- 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