Vikipedio:Projekto matematiko/Tempa hierarkia teoremo

El Vikipedio

Ĉi tiu artikolo montras stilajn aŭ/kaj gramatikajn aŭ/kaj strukturajn problemojn kaj bezonas poluradon por konformi al pli bona nivelo de kvalito. Post plibonigo movu la artikolon al Tempa hierarkia teoremo (eble la nomo mem bezonas korekton) Se la ligo estas ruĝa, vi povas movi la artikolon. Se la ligo estas blua, la alia artikolo pri la temo jam ekzistas kaj tiun kaj ĉi tiun artikolon necasas kunigi.

En komputa komplekseca teorio, la tempaj hierarkiaj teoremoj estas grava (propozicioj, frazoj, ordonoj) (tiu, ke, kiu) certiĝi la ekzisto de certa "peza" (problemoj, problemas) kiu ne povas esti solvita en donita kvanto de tempo. Sekve de tio, por ĉiufoje-barita komplekseca klaso, estas severe pli granda tempo-barita komplekseca klaso, kaj (do, tiel) la rultempa hierarkio de (problemoj, problemas) ne plene kolapso. Unu teoremo (kontraktoj, kontraktas) kun (determinisma, determina) (kalkuladoj, kalkuladas, komputoj, komputas) kaj la alia kun ne-(determinisma, determina) aĵoj. La analoga (teoremoj, teoremas) por spaco estas la spacaj hierarkiaj teoremoj.

Ambaŭ (teoremoj, teoremas) uzi la nocio de tempo-konstruebla funkcio. Funkcio f : N → N estas tempo-konstruebla se tie ekzistas (determinisma, determina) Maŝino de Turing tia (tiu, ke, kiu) por ĉiu n en N, se la maŝino estas startita kun (enigo, enigi) de n aĵoj, ĝi estos halti post precize f(n) (ŝtupoj, ŝtupas, paŝas). Ĉiuj (polinomoj, polinomas) kun nenegativaj integralaj koeficientoj estas tempo-konstruebla, kiel estas eksponentaj funkcioj kiel 2ⁿ.

Enhavo 1 (Determinisma, Determina) tempa hierarkia teoremo 1.1 (Propozicio, Frazo, Ordono) 1.2 Pruvo 1.3 Vastigaĵo 2 Ne-(determinisma, determina) tempa hierarkia teoremo 3 Konsekvencoj 4 Referencoj

[redaktu] (Determinisma, Determina) tempa hierarkia teoremo

[redaktu] (Propozicio, Frazo, Ordono)

La teoremaj ŝtatoj (tiu, ke, kiu): Se f(n) estas tempo-konstruebla funkcio, tiam tie ekzistas decida problemo kiu ne povas esti solvita en plej malbona-(kesto, okazo) (determinisma, determina) tempo f(n) sed povas esti solvita en plej malbona-(kesto, okazo) (determinisma, determina) tempo f(n)². En alia (vortoj, vortas), la komplekseca klaso _DTIME_(f(n)) estas severa subaro de _DTIME_(f(n)²). (Tononomo, Noto, Noti) (tiu, ke, kiu) f(n) estas almenaŭ n, ekde (pli minuskla, pli malgranda) funkcioj estas neniam tempo-konstruebla.

(Eĉ, Ebena, Para) pli ĝenerale, ĝi povas esti montrita (tiu, ke, kiu) se f(n) estas tempo-konstruebla, tiam _DTIME_(o(f(n)/logo f(n))) estas pozitive enhavita en _DTIME_(f(n)). Ekzemple, estas (problemoj, problemas) solvebla ĝustatempe n² sed ne tempo n, ekde n estas en o(n²/logo n²).

[redaktu] Pruvo

Ni inkluzivi ĉi tie pruvo (tiu, ke, kiu) _DTIME_(f(n)) estas severa subaro de _DTIME_(f(2n + 1)³) kiel ĝi estas pli simpla. Vidi la fundo de ĉi tiu sekcio por informo sur kiel al etendi la pruvo al f(n)².

Al pruvi ĉi tiu, ni unua difini lingvo kiel sekvas:

Ĉi tie, M estas (determinisma, determina) Maŝino de Turing, kaj x estas ĝia (enigo, enigi) (la komenca (enhavoj, enhavas) de ĝia bendo). [M] signifas (enigo, enigi) (tiu, ke, kiu) kodas la Maŝino de Turing M. Estu m esti la amplekso de la opo ([M], x).

Ni scii (tiu, ke, kiu) ni povas decidi anaro de H_f per vojo de (determinisma, determina) Maŝino de Turing (tiu, ke, kiu) unua kalkulas f(|x|), tiam skribas ekster (linio, vico) de _0s_ de (tiu, ke, kiu) longo, kaj tiam uzas ĉi tiu (linio, vico) de _0s_ kiel "horloĝo" aŭ "nombrilo" al simuli M por maksimume (tiu, ke, kiu) multaj (ŝtupoj, ŝtupas, paŝas). Je ĉiu (ŝtupo, paŝi), la simulanta maŝino (bezonas, bezonoj) al trarigardi la difino de M al decidi kio la venonta ago devus esti. Ĝi estas sekura al diri (tiu, ke, kiu) ĉi tiu prenas maksimume f(m)³ (operacioj, operacias), (do, tiel)

La cetera la pruvo estos montri (tiu, ke, kiu)

tiel ke se ni (anstataŭa, anstataŭigi) 2n + 1 por m, ni preni la deziris rezulto. Estu ni alpreni (tiu, ke, kiu) H_f estas en ĉi tiu tempa komplekseca klaso, kaj ni estos provi al atingi kontraŭdiro.

Se H_f estas en ĉi tiu tempa komplekseca klaso, ĝi (meznombroj, meznombras, signifas) ni povas konstrui iu maŝino K kiu, donita iu maŝina priskribo [M] kaj (enigo, enigi) x, decidas ĉu la opo ([M], x) estas en H_f en .

Pro tio ni povas uzi ĉi tiu K al konstrui alia maŝino, N, kiu prenas maŝina priskribo [M] kaj (kuras, rulas) K sur la opo ([M], [M]), kaj tiam akceptas nur se K (malakceptas, malaprobas), kaj (malakceptas, malaprobas) se K akceptas. Se nun n estas la longo de la (enigo, enigi) al N, tiam m (la longo de la (enigo, enigi) al K) estas dufoje n plus iu disigila simbolo, (do, tiel) m = 2n + 1. N's (kuro, kurante, rulante) tempo estas tial .

Nun se ni nutri [N] kiel (enigo, enigi) enen N sin (kiu (konstruas, faras) n la longo de [N]) kaj (demandi, peti) la demando ĉu N akceptas ĝia posedi priskribo kiel (enigo, enigi), ni preni:

• Se N akceptas [N] (kiu ni scii ĝi faras en maksimume f(n) (operacioj, operacias)), ĉi tiu (meznombroj, meznombras, signifas) (tiu, ke, kiu) K (malakceptas, malaprobas) ([N], [N]), (do, tiel) ([N], [N]) estas ne en H_f, kaj tial N ne akcepti [N] en f(n) (ŝtupoj, ŝtupas, paŝas). Kontraŭdiro!
• Se N (malakceptas, malaprobas) [N] (kiu ni scii ĝi faras en maksimume f(n) (operacioj, operacias)), ĉi tiu (meznombroj, meznombras, signifas) (tiu, ke, kiu) K akceptas ([N], [N]), (do, tiel) ([N], [N]) estas en H_f, kaj tial N faras akcepti [N] en f(n) (ŝtupoj, ŝtupas, paŝas). Kontraŭdiro!

Ni tial konkludi (tiu, ke, kiu) la maŝino K ne ekzisti, kaj (do, tiel)

[redaktu] Vastigaĵo

La legilo (majo, povas) havi komprenita (tiu, ke, kiu) la pruvo estas pli simpla ĉar ni havi elektita simpla Maŝino de Turing simulado por kiu ni povas esti certa (tiu, ke, kiu)

Ĝi havas estas montrita [1] (tiu, ke, kiu) pli kompetenta modelo de simulado ekzistas kiu _establishes_ (tiu, ke, kiu)

sed ekde ĉi tiu modelo de simulado estas iom koncernata, ĝi estas ne inkluzivita ĉi tie.

[redaktu] Ne-(determinisma, determina) tempa hierarkia teoremo

Se g(n) estas tempo-konstruebla funkcio, kaj f(n+1) = o(g(n)), tiam tie ekzistas decida problemo kiu ne povas esti solvita en ne-(determinisma, determina) tempo f(n) sed povas esti solvita en ne-(determinisma, determina) tempo g(n). En alia (vortoj, vortas), la komplekseca klaso _NTIME_(f(n)) estas severa subaro de _NTIME_(g(n)).

[redaktu] Konsekvencoj

La tempaj hierarkiaj teoremoj garantii (tiu, ke, kiu) la (determinisma, determina) kaj ne-(determinisma, determina) versio de la eksponenta funkcia hierarkio estas aŭtentika (hierarkioj, hierarkias): en alia (vortoj, vortas) P ⊂ _EXPTIME_ ⊂ 2-_EXP_ ⊂ ..., kaj (Np, NP) ⊂ _NEXPTIME_ ⊂ 2-_NEXP_ ⊂ ...

La teoremo ankaŭ garantias (tiu, ke, kiu) estas (problemoj, problemas) en P postulanta arbitre grandaj eksponentoj al solvi; en alia (vortoj, vortas), P ne kolapso al _DTIME_(n^k) por (ĉiu, iu) (fiksis, neŝanĝebligita) k. Ekzemple, estas (problemoj, problemas) solvebla en O(n⁵⁰⁰⁰) tempo sed ne O(n⁴⁹⁹⁹) tempo. Ĉi tiu estas unu argumento kontraŭ konsideranta P al esti praktika klaso de (algoritmoj, algoritmas). Ĉi tiu estas bedaŭrinda, ekde se tia kolapso farita okazi, ni povita (dedukti, konkludi) (tiu, ke, kiu) P ≠ _PSPACE_, ekde ĝi estas konata teoremo (tiu, ke, kiu) _DTIME_(f(n)) estas severe enhavita en _DSPACE_(f(n)).

Tamen, la tempaj hierarkiaj teoremoj provizi ne (meznombroj, meznombras, signifas) al (rilati, rakonti) (determinisma, determina) kaj ne-(determinisma, determina) komplekseco, aŭ tempo kaj spaca komplekseco, (do, tiel) ili disĵeti ne lumo sur la granda nesolvita (demandoj, demandas) de komplikteorio: ĉu P kaj (Np, NP), (Np, NP) kaj _PSPACE_, _PSPACE_ kaj _EXPTIME_, aŭ _EXPTIME_ kaj _NEXPTIME_ estas egala ĉu ne.

[redaktu] Referencoj

• _Stephen_ Kuiri (1972). A hierarkio por _nondeterministic_ tempa komplekseco. Paperoj de la kvara ĉiujara _ACM_ simpozio sur Teorio de komputanta, _pp_.187–192.
• Paĝoj 310–313 de sekcio 9.1: Hierarkio (teoremoj, teoremas).
• Sekcio 7.2: La Hierarkia Teoremo, _pp_.143–146.