Ĉu problemo povas esti en NP-kompleksecklaso se ekzistas nedeterminisma turnmaŝino kiu solvos ĝin en polinoma tempo
La demando "Ĉu problemo povas esti en NP-kompleksecklaso se ekzistas ne-determinisma Turing-maŝino kiu solvos ĝin en polinoma tempo?" tuŝas fundamentajn konceptojn en komputa komplekseca teorio. Por trakti ĉi tiun demandon amplekse, ni devas konsideri la difinojn kaj karakterizaĵojn de la NP-kompleksecklaso kaj la rolon de nedeterminismaj Turing-maŝinoj (NDTMoj).
Difino de NP
La klaso NP (nedeterminisma polinoma tempo) konsistas el decidproblemoj por kiuj antaŭfiksita solvo povas esti kontrolita kiel ĝusta aŭ malĝusta en polinoma tempo per determinisma Turing-maŝino (DTM). Formale, decidproblemo estas en NP se ekzistas polinomtempa konfirmalgoritmo kiu povas kontroli la ĝustecon de antaŭfiksita atestilo (aŭ atestanto) por kazo de la problemo.
Ne-Determinismaj Turing-Maŝinoj
Ne-determinisma Turing-maŝino estas teoria modelo de komputado kiu etendas la kapablojn de determinisma Turing-maŝino. Male al DTM, kiu sekvas ununuran komputilan padon difinitan per sia transirfunkcio, NDTM povas trakti multoblajn komputilajn padojn samtempe. Je ĉiu paŝo, NDTM povas "elekti" el aro de eblaj transiroj, efike esplorante multajn eblajn komputojn paralele.
Polinoma-Tempo Solvebleco de NDTMoj
Problemo laŭdire estas solvebla per NDTM en polinoma tempo se ekzistas ne-determinisma algoritmo kiu povas trovi solvon al la problemo ene de kelkaj ŝtupoj kiu estas polinomo en la grandeco de la enigaĵo. Tio signifas ke por iu kazo de la problemo, la NDTM povas esplori komputilan padon kiu kondukas al solvo en polinoma tempo.
Rilato Inter NP kaj NDTMoj
La klaso NP povas esti ekvivalente difinita laŭ NDTMoj. Specife, decidproblemo estas en NP se kaj nur se ekzistas NDTM kiu povas solvi la problemon en polinoma tempo. Tiu ekvivalento ekestiĝas de la fakto ke NDTM povas diveni atestilon ne-determinisme kaj tiam kontroli ĝin determinisme en polinoma tempo.
Por ilustri ĉi tion per ekzemplo, konsideru la konatan NP-kompletan problemon, la Bulea kontentigproblemo (SAT). Donita Bulea formulo en konjunkcia normala formo (CNF), la tasko estas determini ĉu ekzistas asigno de vervaloroj al la variabloj kiuj faras la formulon vera. NDTM povas solvi SAT en polinoma tempo ne-determinisme divenante taskon de vervaloroj kaj tiam determinisme kontrolante ĉu la tasko kontentigas la formulon. La konfirmpaŝo, kiu implikas taksi la formulon sub la divenita tasko, povas esti farita en polinoma tempo.
Implicoj de Polynomial-Time Solvability de NDTMoj
Surbaze de ĉi-supraj difinoj kaj la ekvivalento inter NP kaj polinomtempa solvebleco de NDTMoj, ni povas konkludi ke se ekzistas NDTM kiu solvas problemon en polinoma tempo, tiam la problemo estas ja en NP. Ĉi tio estas ĉar la ekzisto de tia NDTM implicas ke ekzistas polinomtempa konfirmalgoritmo por la problemo. La ne-determinisma divenfazo de la NDTM egalrilatas al la generacio de atestilo, kaj la determinisma konfirmfazo egalrilatas al la polinom-tempa konfirmalgoritmo.
Pliaj Konsideroj kaj Ekzemploj
Por plue klarigi ĉi tiun koncepton, ni konsideru kromajn ekzemplojn de problemoj en NP kaj ilian rilaton kun NDTMoj:
1. Hamiltoniana Voja Problemo: Donita grafeon, la hamiltoniana Path-problemo demandas ĉu ekzistas pado kiu vizitas ĉiun verticon ekzakte unufoje. NDTM povas solvi ĉi tiun problemon en polinoma tempo ne-determinisme divenante sekvencon de verticoj kaj tiam kontrolante ĉu la sekvenco formas validan Hamiltonianan vojon. La konfirmpaŝo implikas kontroli la apudecon de sinsekvaj verticoj kaj certigi ke ĉiu vertico estas vizitita ekzakte unufoje, kiuj ambaŭ povas esti faritaj en polinoma tempo.
2. Problemo de sumo de subaro: Donita aro de entjeroj kaj celsumo, la Subaro Sumo-problemo demandas ĉu ekzistas subaro de la entjeroj kiu sumas al la celo. NDTM povas solvi ĉi tiun problemon en polinoma tempo ne-determinisme divenante subaron de la entjeroj kaj tiam kontrolante ĉu la sumo de la subaro egalas al la celo. La konfirmpaŝo implikas sumigi la elementojn de la divenita subaro, kiu povas esti farita en polinoma tempo.
3. Grafika Koloriga Problemo: Donita grafeon kaj kelkajn kolorojn, la Graph Coloring-problemo demandas ĉu estas eble kolorigi la verticojn de la grafeo tia ke neniuj du apudaj verticoj kunhavas la saman koloron. NDTM povas solvi ĉi tiun problemon en polinoma tempo ne-determinisme asignante kolorojn al la verticoj kaj tiam kontrolante ĉu la kolorigo estas valida. La konfirmpaŝo implikas kontroli la kolorojn de apudaj verticoj, kiu povas esti farita en polinoma tempo.
konkludo
En lumo de la difinoj kaj ekzemploj provizitaj, estas klare ke problemo ja povas esti en la NP-kompleksecklaso se ekzistas ne-determinisma Turing-maŝino kiu solvos ĝin en polinoma tempo. Tiu rilato estas bazŝtono de komputila komplekseca teorio kaj substrekas la ekvivalenton inter polinomtempa solvebleco de NDTMoj kaj membreco en la NP-klaso.
Aliaj lastatempaj demandoj kaj respondoj pri komplekseco:
- Ĉu PSPACE-klaso ne egalas al la EXPSPACE-klaso?
- Ĉu P-kompleksecklaso estas subaro de PSPACE-klaso?
- Ĉu ni povas pruvi ke Np kaj P-klaso estas la samaj trovante efikan polinomsolvon por iu NP kompleta problemo sur determinisma TM?
- Ĉu la NP-klaso povas esti egala al la EXPTIME-klaso?
- Ĉu ekzistas problemoj en PSPACE por kiuj ne estas konata NP-algoritmo?
- Ĉu SAT-problemo povas esti NP kompleta problemo?
- NP estas la klaso de lingvoj kiuj havas polinomajn tempokontrolilojn
- Ĉu P kaj NP efektive estas la sama komplekseca klaso?
- Ĉu ĉiu kunteksto libera lingvo en la P-kompleksecklaso?
- Ĉu ekzistas kontraŭdiro inter la difino de NP kiel klaso de decidproblemoj kun polinomtempaj kontroliloj kaj la fakto ke problemoj en la klaso P ankaŭ havas polinomtempajn kontrolilojn?
Rigardu pliajn demandojn kaj respondojn en Komplekseco