Ar kiekviena savavališka problema gali būti išreikšta kalba?
Skaičiavimo sudėtingumo teorijos srityje problemų reiškimo kalbomis koncepcija yra esminė. Norėdami išspręsti šį klausimą, turime apsvarstyti teorinius skaičiavimo ir formalių kalbų pagrindus.
„Kalba“ skaičiavimo sudėtingumo teorijoje yra eilučių rinkinys per baigtinę abėcėlę. Tai formali konstrukcija, kurią gali atpažinti skaičiavimo modelis, pavyzdžiui, Tiuringo mašina. Ši sąvoka yra pagrįsta formaliosios kalbos teorija, kuri tiria formalių kalbų sintaksines savybes ir jų klasifikaciją.
Norėdami suprasti, ar kiekviena savavališka problema gali būti išreikšta kaip kalba, pirmiausia turime išsiaiškinti, ką reiškia „savavališka problema“. Skaičiavimo terminais, problema paprastai reiškia sprendimo problemą arba funkcijos problemą. Sprendimo problema užduoda „taip“/„ne“ klausimą apie įvestį, o funkcijos problema reikalauja apskaičiuoti konkrečią tam tikros įvesties išvestį.
Sprendimo problemų atveju ryšys su kalbomis yra paprastas. Sprendimo problema iš tiesų gali būti išreikšta kalba. Apsvarstykite sprendimo problemą ( P ), kuri klausia, ar tam tikra įvestis ( x ) priklauso aibei ( S ). Šią problemą galima pavaizduoti kalba ( L ), susidedančia iš visų eilučių ( x ), kurios atsakymas į ( P(x) ) yra "taip". Todėl sprendimo problema ( P ) yra lygiavertė kalbai ( L ).
Pavyzdžiui, panagrinėkime sprendimo problemą, kaip nustatyti, ar tam tikra dvejetainė eilutė reiškia lyginį skaičių. Kalba, atitinkanti šią problemą, yra visų dvejetainių eilučių, kurios baigiasi '0', rinkinys, nes dvejetainis skaičius yra net tada ir tik tada, kai jo mažiausiai reikšmingas bitas yra 0. Taigi problemą galima išreikšti kalba ( L = { x {0,1}^* vidurio x tekstas{ baigiasi } 0 } ).
Kita vertus, funkcijų problemos yra labiau niuansuotos. Funkcijos problemai reikia apskaičiuoti vertę, o ne priimti dvejetainį sprendimą. Norint išreikšti funkcijos problemą kaip kalbą, vienas iš būdų yra atsižvelgti į funkcijos grafiką. Funkcijos ( f ) grafikas yra sutvarkytų porų aibė ( (x, f(x)) ). Šis rinkinys gali būti vertinamas kaip kalba per abėcėlę, kurioje yra ir įvesties, ir išvesties simboliai.
Pavyzdžiui, apsvarstykite sveikojo skaičiaus kvadrato skaičiavimo funkcijos problemą. Šios funkcijos grafikas yra porų rinkinys ( { (x, x^2) mid x in mathbb{Z} } ). Šis rinkinys gali būti užkoduotas kaip kalba per atitinkamą abėcėlę. Tačiau šis vaizdavimas yra sudėtingesnis nei paprastas sprendimų problemų vaizdavimas.
Gebėjimas reikšti problemas kaip kalbas yra galinga sąvoka, nes leidžia naudoti formaliosios kalbos teoriją ir automatų teoriją skaičiavimo problemoms analizuoti. Kalbų klasės, atpažįstamos skirtingais skaičiavimo modeliais, pavyzdžiui, įprastos kalbos, be konteksto kalbos ir rekursyviai suskaičiuojamos kalbos, atitinka skirtingas sprendimų problemų klases.
Pavyzdžiui, įprastos kalbos yra tos, kurias gali atpažinti baigtiniai automatai. Jie atitinka sprendimų problemas, kurias galima išspręsti turint ribotą atminties kiekį. Nekontekstinės kalbos, atpažįstamos išspaudimo automatų, gali reikšti problemas, kurioms reikalinga į krūvą panaši atminties struktūra. Rekursyviai išvardijamos kalbos, kurias atpažįsta Turingo mašinos, atitinka problemas, kurias gali išspręsti bendrosios paskirties kompiuteris su neribota atmintimi.
Norėdami toliau iliustruoti ryšį tarp problemų ir kalbų, apsvarstykite garsiąją problemą, kaip nustatyti, ar tam tikra eilutė yra palindromas. Palindromas yra eilutė, kuri skaito tą pačią pirmyn ir atgal. Sprendimo problema patikrinti, ar eilutė yra palindromas, gali būti išreikšta kaip kalba (L = { x Sigma^* mid x = x^R } ), kur ( x^R ) reiškia ( x ) atvirkštinę pusę.
Be to, skaičiavimo sudėtingumo teorijos problemų mažinimo samprata remiasi problemų išreiškimu kalbomis. Sumažinimas iš problemos (A) į problemą (B) yra būdas (A) paversti (B) egzempliorius taip, kad sprendimas (B) leistų mums išspręsti (A). Ši transformacija dažnai išreiškiama kaip funkcija, kuri susieja eilutes kalba ( A ) su eilutėmis ( B ) kalba.
Pavyzdžiui, problema nustatyti, ar grafikas yra dvišalis, gali būti sumažintas iki problemos, kaip nustatyti, ar grafikas turi tinkamą 2 spalvą. Šis sumažinimas gali būti išreikštas kaip funkcija, kuri paverčia dvišališkumo problemos atvejus į dviejų spalvų problemos atvejus. Kalba, atitinkanti dvišališkumo problemą, yra visų grafų kodų, vaizduojančių dvišalius grafikus, rinkinys, o kalba, atitinkanti 2 spalvų spalvinimo problemą, yra visų grafų kodų rinkinys, turintis tinkamą 2 spalvą.
Be to, NP užbaigtumo teorija labai priklauso nuo problemų išreiškimo kalbomis. Problema yra NP-baigta, jei ji yra NP ir kiekviena NP problema gali būti sumažinta iki jos daugianario laiku. Klasė NP susideda iš sprendimo problemų, kurių atsakymą "taip" galima patikrinti nedeterministiniu daugianario laiko algoritmu. Šių problemų išreiškimas kalbomis leidžia naudoti formalius metodus NP užbaigtumui įrodyti.
Pavyzdžiui, SAT problema, kuri klausia, ar tam tikra loginė formulė yra patenkinama, yra NP užbaigta. SAT atitinkanti kalba yra visų patenkinamų loginių formulių koduotų rinkinys. Įrodžius, kad kita problema, pvz., Clique problema, yra visiškai NP, reikia parodyti, kad SAT gali būti sumažintas iki Clique. Šis sumažinimas išreiškiamas kaip funkcija, kuri logines formules paverčia grafų koduotėmis.
Nors sprendimų problemos gali būti tiesiogiai išreikštos kalbomis, funkcijų problemos reikalauja sudėtingesnio vaizdavimo, dažnai apimančio funkcijos grafiką. Gebėjimas reikšti problemas kaip kalbas yra skaičiavimo sudėtingumo teorijos kertinis akmuo, leidžiantis naudoti formaliosios kalbos teoriją problemoms analizuoti ir klasifikuoti. Šis metodas remiasi daugeliu pagrindinių sąvokų, tokių kaip redukcijos, NP užbaigtumas ir kalbų, atpažįstamų skirtingais skaičiavimo modeliais, klasifikacija.
Kiti naujausi klausimai ir atsakymai apie EITC/IS/CCTF skaičiavimo sudėtingumo teorijos pagrindai:
- Atsižvelgiant į nedeterministinius PDA, būsenų superpozicija yra įmanoma pagal apibrėžimą. Tačiau nedeterministiniai PDA turi tik vieną krūvą, kuri negali būti kelių būsenų vienu metu. Kaip tai įmanoma?
- Koks yra PDA, naudojamo tinklo srautui analizuoti ir modeliams, rodantiems galimus saugumo pažeidimus, pavyzdys?
- Ką reiškia, kad viena kalba yra galingesnė už kitą?
- Ar Turingo mašina atpažįsta kontekstui jautrias kalbas?
- Kodėl kalba U = 0^n1^n (n>=0) yra netaisyklinga?
- Kaip apibrėžti FSM, atpažįstantį dvejetaines eilutes su lyginiu simbolių skaičiumi '1', ir parodyti, kas su juo atsitinka apdorojant įvesties eilutę 1011?
- Kaip nedeterminizmas veikia perėjimo funkciją?
- Ar įprastos kalbos lygiavertės baigtinių būsenų mašinoms?
- Ar PSPACE klasė nėra lygi EXPSPACE klasei?
- Ar algoritmiškai apskaičiuojama problema yra problema, kurią pagal Church-Turing tezę galima apskaičiuoti Tiuringo mašina?
Peržiūrėkite daugiau klausimų ir atsakymų EITC/IS/CCTF skaičiavimo sudėtingumo teorijos pagrinduose