Davlatning murakkabligi - State complexity - Wikipedia

Davlatning murakkabligi maydonidir nazariy informatika mavhum avtomatlarning o'lchamlari bilan ishlash, masalan, har xil cheklangan avtomatlar.Mintaqadagi klassik natija bu an simulyatsiya ${ displaystyle n}$- davlatnoaniq cheklangan avtomat tomonidan deterministik cheklangan avtomat to'liq talab qilinadi ${ displaystyle 2 ^ {n}}$ eng yomon holatda davlatlar.

Cheklangan avtomatlarning variantlari orasidagi o'zgarish

Sonlu avtomatlar bo'lishi mumkindeterministik vanoaniq, bir tomonlama (DFA, NFA) va ikki tomonlama (2DFA, 2NFA). Boshqa tegishli sinflaraniq (O'FA),o'z-o'zini tekshirish (SVFA) va o'zgaruvchan (AFA) cheklangan avtomatlar.Bu avtomatlar ham ikki tomonlama bo'lishi mumkin (2UFA, 2SVFA, 2AFA).

Ushbu mashinalarning barchasi aniq qabul qilishi mumkin oddiy tillar Shu bilan birga, bir xil tilni qabul qilish uchun zarur bo'lgan avtomat turlarining har xil o'lchamlari (ularning holatlari sonida o'lchanadi) har xil bo'lishi mumkin. Har qanday ikki turdagi cheklangan avtomatlar uchun davlatning murakkabligi ular orasida butun sonli funktsiya mavjud ${ displaystyle f}$qayerda ${ displaystyle f (n)}$ har bir tilni tanib olish uchun ikkinchi turdagi avtomatlarning eng kam sonli holati ${ displaystyle n}$- birinchi turdagi davlat avtomati. Quyidagi natijalar ma'lum.

• NFA dan DFA: ${ displaystyle 2 ^ {n}}$ davlatlar. Bu kichik qurilish tomonidan Rabin va Skott,^[1] tomonidan optimal isbotlangan Lupanov.^[2]

• O'FA - DFA: ${ displaystyle 2 ^ {n}}$ davlatlar, qarang Leung,^[3] Shmidt tomonidan ilgari pastki chegara^[4] kichikroq edi.
• O'FAga NFA: ${ displaystyle 2 ^ {n} -1}$ davlatlar, qarang Leung.^[3] Shmidt tomonidan ilgari kichikroq chegara mavjud edi.^[4]
• SVFA dan DFA: ${ displaystyle Theta (3 ^ {n / 3})}$ davlatlar, qarang Jiraskova va Pigizzini^[5]
• 2DFA dan DFA: ${ displaystyle n (n ^ {n} - (n-1) ^ {n})}$ davlatlar, qarang Kaputsis.^[6] Avvalroq qurilish Cho'pon^[7] ko'proq davlatlardan foydalangan va undan oldinroq Mur tomonidan quyi chegaralar^[8] kichikroq edi.
• 2DFA dan NFA: ${ displaystyle { binom {2n} {n + 1}} = O ({ frac {4 ^ {n}} { sqrt {n}}})}$, Kaputsisga qarang.^[6] Avvalroq qurilish Birget ^[9] ko'proq davlatlardan foydalangan.
• 2NFA dan NFA: ${ displaystyle { binom {2n} {n + 1}}}$, Kaputsisga qarang.^[6]
  • 2NFA-dan NFA-ga qo'shimchani qabul qilish: ${ displaystyle O (4 ^ {n})}$ davlatlar, qarang Vardi.^[10]
• AFA dan DFA: ${ displaystyle 2 ^ {2 ^ {n}}}$ davlatlar, qarang Chandra, Kozen va Stokmeyer.^[11]
• AFA dan NFA: ${ displaystyle 2 ^ {n}}$ shtatlari, qarang Fellax, Yurgensen va Yu.^[12]
• 2AFA dan DFA: ${ displaystyle 2 ^ {n2 ^ {n}}}$, qarang Ladner, Lipton va Stokmeyer.^[13]
• 2AFA dan NFA: ${ displaystyle 2 ^ { Theta (n log n)}}$, qarang Geffert va Okhotin.^[14]

2DFA va 2NFA muammolari va logaritmik bo'shliq

Kompyuter fanida hal qilinmagan muammo: Har bir narsani qiladi ${ displaystyle n}$- davlat 2NFA ning ekvivalenti bor ${ displaystyle operatorname {poly} (n)}$- davlat 2DFA? (kompyuter fanida hal qilinmagan muammolar)

Barcha 2NFA-larni ko'p sonli holatlar bilan 2DFA-ga aylantirish mumkinmi, ya'ni polinom mavjudmi, bu ochiq muammo. ${ displaystyle p (n)}$har bir kishi uchun shunday ${ displaystyle n}$- davlat 2NFA mavjud a ${ displaystyle p (n)}$- davlat 2DFA. Muammoni Sakoda va Sipser,^[15]uni kim bilan taqqoslagan P va NP muammo hisoblash murakkabligi nazariyasi.Berman va Lingalar^[16] bu muammo bilan rasmiy aloqani aniqladi L va boshqalar NL ochiq muammo.Bu munosabatlar yanada yaxshilandi Kaputsis.^[17]

Cheklangan avtomatlar uchun operatsiyalarning davlat murakkabligi

Tillarda ikkilik muntazamlikni saqlash operatsiyasi berilgan ${ displaystyle circ}$va avtomatika X oilasi (DFA, NFA va boshqalar), davlatning murakkabligi ${ displaystyle circ}$butun sonli funktsiya ${ displaystyle f (m, n)}$ shu kabi

• har bir m holatidagi X avtomat A va n holatdagi X avtomat B uchun an mavjud ${ displaystyle f (m, n)}$- davlat X-avtomati ${ displaystyle L (A) circ L (B)}$va
• m, n butun sonlar uchun m-holatli X avtomat A va n holatli X avtomat B mavjud, shunday qilib har bir X avtomat uchun ${ displaystyle L (A) circ L (B)}$ kamida bo'lishi kerak ${ displaystyle f (m, n)}$ davlatlar.

Shunga o'xshash ta'rif har qanday sonli argumentlar bilan operatsiyalar uchun qo'llaniladi.

DFAlar uchun operatsiyalarning davlat murakkabligi bo'yicha birinchi natijalar Maslov tomonidan nashr etilgan^[18]va Yu, Chjuan va Salomaa.^[19]Xolzer va Kutrib^[20]asosiy operatsiyalar bo'yicha ma'lum natijalar quyida keltirilgan.

Ittifoq

Agar til bo'lsa ${ displaystyle L_ {1}}$ davlat va tilni talab qiladi ${ displaystyle L_ {2}}$ n holatini talab qiladi, qancha shtat ${ displaystyle L_ {1} kubok L_ {2}}$ talab qiladimi?

• DFA: ${ displaystyle mn}$ davlatlar, qarang Maslov^[18] va Yu, Zhuang va Salomaa.^[19]
• NFA: ${ displaystyle m + n + 1}$ shtatlari, Xolzer va Kutribga qarang.^[20]
• O'FA: o'rtasida ${ displaystyle mn + m + n}$ va ${ displaystyle O (n2 ^ {0.79m})}$ shtatlari, qarang Jirasek, Jiraskova va Sebey.^[21]
• SVFA: ${ displaystyle mn}$ shtatlari, qarang Jirasek, Jiraskova va Sabari.^[22]
• 2DFA: o'rtasida ${ displaystyle m + n}$ va ${ displaystyle 4m + n + 4}$ shtatlari, qarang Kunc va Okhotin.^[23]
• 2NFA: ${ displaystyle m + n}$ shtatlari, qarang Kunc va Okhotin.^[24]

Kesishma

Qancha shtatlar ${ displaystyle L_ {1} cap L_ {2}}$ talab qiladimi?

• DFA: ${ displaystyle mn}$ davlatlar, qarang Maslov^[18] va Yu, Zhuang va Salomaa.^[19]
• NFA: ${ displaystyle mn}$ shtatlari, Xolzer va Kutribga qarang.^[20]
• O'FA: ${ displaystyle mn}$ shtatlari, qarang Jirasek, Jiraskova va Sebey.^[21]
• SVFA: ${ displaystyle mn}$ shtatlari, qarang Jirasek, Jiraskova va Sabari.^[22]
• 2DFA: o'rtasida ${ displaystyle m + n}$ va ${ displaystyle m + n + 1}$ shtatlari, qarang Kunc va Okhotin.^[23]
• 2NFA: o'rtasida ${ displaystyle m + n}$ va ${ displaystyle m + n + 1}$ shtatlari, qarang Kunc va Okhotin.^[24]

To'ldirish

Agar L tili n statest talab qilsa, unda nechta holat to'ldiruvchi talab qiladimi?

• DFA: ${ displaystyle n}$ qabul qiluvchi va rad etgan davlatlarni almashtirish orqali.
• NFA: ${ displaystyle 2 ^ {n}}$ shtatlari, Birget-ga qarang.^[25]
• O'FA: hech bo'lmaganda ${ displaystyle n ^ {2-o (1)}}$ va ko'pi bilan ${ displaystyle O (2 ^ {0.79n})}$ shtatlari, Okhotinga qarang^[26] pastki chegara va Jireshek, Jiraskova va Sebey uchun^[21] yuqori chegara uchun. Raskin^[27] yaqinda super polinomial pastki chegarani isbotladi.
• SVFA: ${ displaystyle n}$ qabul qiluvchi va rad etgan davlatlarni almashtirish orqali.
• 2DFA: hech bo'lmaganda ${ displaystyle n}$ va ko'pi bilan ${ displaystyle 4n}$ shtatlari, Geffert, Mereghetti va Pigizzini-ga qarang.^[28]

Birlashtirish

Qancha shtatlar ${ displaystyle L_ {1} L_ {2} = {w_ {1} w_ {2} mid w_ {1} in L_ {1}, w_ {2} in L_ {2} }}$ talab qiladimi?

• DFA: ${ displaystyle m cdot 2 ^ {n} -2 ^ {n-1}}$ davlatlar, qarang Maslov ^[18] va Yu, Zhuang va Salomaa.^[19]
• NFA: ${ displaystyle m + n}$ shtatlari, Xolzer va Kutribga qarang.^[20]
• O'FA: ${ displaystyle { frac {3} {4}} 2 ^ {m + n} -1}$ shtatlari, qarang Jirasek, Jiraskova va Sebey.^[21]
• SVFA: ${ displaystyle Theta (3 ^ {n / 3} 2 ^ {m})}$ shtatlari, qarang Jirasek, Jiraskova va Sabari.^[22]
• 2DFA: hech bo'lmaganda ${ displaystyle { frac {2 ^ { Omega (n)}} { log m}}}$ va ko'pi bilan ${ displaystyle 2m ^ {m + 1} cdot 2 ^ {n ^ {n + 1}}}$ shtatlari, qarang Jiraskova va Okhotin.^[29]

Kleene yulduzi

• DFA: ${ displaystyle { frac {3} {4}} 2 ^ {n}}$ davlatlar, qarang Maslov^[18] va Yu, Zhuang va Salomaa.^[19]
• NFA: ${ displaystyle n + 1}$ shtatlari, Xolzer va Kutribga qarang.^[20]
• O'FA: ${ displaystyle { frac {3} {4}} 2 ^ {n}}$ shtatlari, qarang Jirasek, Jiraskova va Sebey.^[21]
• SVFA: ${ displaystyle { frac {3} {4}} 2 ^ {n}}$ shtatlari, qarang Jirasek, Jiraskova va Sabari.^[22]
• 2DFA: hech bo'lmaganda ${ displaystyle { frac {1} {n}} 2 ^ {{ frac {n} {2}} - 1}}$ va ko'pi bilan ${ displaystyle 2 ^ {O (n ^ {n + 1})}}$ shtatlari, qarang Jiraskova va Okhotin.^[29]

Orqaga qaytarish

• DFA: ${ displaystyle 2 ^ {n}}$ davlatlar, qarang Mirkin,^[30] Leys,^[31] va Yu, Zhuang va Salomaa.^[19]
• NFA: ${ displaystyle n + 1}$ shtatlari, Xolzer va Kutribga qarang.^[20]
• O'FA: ${ displaystyle n}$ davlatlar.
• SVFA: ${ displaystyle 2n + 1}$ shtatlari, qarang Jirasek, Jiraskova va Sabari.^[22]
• 2DFA: o'rtasida ${ displaystyle n + 1}$ va ${ displaystyle n + 2}$ shtatlari, Jiraskova va Okhotin qarang.^[29]

Bitta alifbo bo'yicha cheklangan avtomatlar

Bir harfli cheklangan avtomatlarning davlat murakkabligi (unary) tomonidan kashshof qilingan alifbo Chrobak,^[32] ko'p harfli ishdan farq qiladi.

Ruxsat bering ${ displaystyle g (n) = e ^ { Theta ({ sqrt {n ln n}})}}$ bo'lishi Landau funktsiyasi.

Modellar orasidagi o'zgarish

Bitta harfli alifbo uchun har xil turdagi avtomatlarning o'zgarishi ba'zan umumiy holatga qaraganda samaraliroq bo'ladi.

• NFA dan DFA: ${ displaystyle g (n) + O (n ^ {2})}$ davlatlar, qarang Chrobak.^[32]
• 2DFA dan DFA: ${ displaystyle g (n) + O (n)}$ davlatlar, qarang Chrobak^[32] va Kunc va Oxotin.^[33]
• 2NFA dan DFA: ${ displaystyle O (g (n))}$ davlatlar, qarang Mereghetti va Pigizzini.^[34] va Geffert, Mereghetti va Pigizzini.^[35]
• NFA dan 2DFAgacha: ko'pi bilan ${ displaystyle O (n ^ {2})}$ davlatlar, qarang Chrobak.^[32]
• 2NFA dan 2DFA gacha: ko'pi bilan ${ displaystyle n ^ {O ( log n)}}$ usulini amalga oshirish orqali isbotlangan Savitch teoremasi, Geffert, Mereghetti va Pigitsziniga qarang.^[35]
• O'FA - DFA: ${ displaystyle e ^ { Theta ({ sqrt [{3}] {n ( ln n) ^ {2}}})}}$, Oxotinga qarang.^[26]
• O'FAga NFA: ${ displaystyle g (n) + O (n ^ {2})}$, Oxotinga qarang.^[26]

Ittifoq

• DFA: ${ displaystyle mn}$ shtatlari, Yu, Zhuang va Salomaa-ga qarang.^[19]
• NFA: ${ displaystyle m + n + 1}$ shtatlari, Xolzer va Kutribga qarang.^[20]
• 2DFA: o'rtasida ${ displaystyle m + n}$ va ${ displaystyle 2m + n + 4}$ shtatlari, qarang Kunc va Okhotin.^[23]
• 2NFA: ${ displaystyle m + n}$ shtatlari, qarang Kunc va Okhotin.^[24]

Kesishma

• DFA: ${ displaystyle mn}$ shtatlari, Yu, Zhuang va Salomaa-ga qarang.^[19]
• NFA: ${ displaystyle mn}$ shtatlari, Xolzer va Kutribga qarang.^[20]
• 2DFA: o'rtasida ${ displaystyle m + n}$ va ${ displaystyle m + n + 1}$ shtatlari, qarang Kunc va Okhotin.^[23]
• 2NFA: o'rtasida ${ displaystyle m + n}$ va ${ displaystyle m + n + 1}$ shtatlari, qarang Kunc va Okhotin.^[24]

To'ldirish

• DFA: ${ displaystyle n}$ davlatlar.
• NFA: ${ displaystyle g (n) + O (n ^ {2})}$ davlatlar, Xolzer va Kutrib.^[20]
• O'FA: hech bo'lmaganda ${ displaystyle n ^ {2-o (1)}}$ va ko'pi bilan ${ displaystyle e ^ { Theta ({ sqrt [{3}] {n ( ln n) ^ {2}}})}}$ shtatlari, Okhotinga qarang.^[26]
• 2DFA: hech bo'lmaganda ${ displaystyle n}$ va ko'pi bilan ${ displaystyle 2n + 3}$ shtatlari, qarang Kunc va Okhotin.^[23]
• 2NFA: hech bo'lmaganda ${ displaystyle n}$ va ko'pi bilan ${ displaystyle O (n ^ {8})}$ davlatlar. Yuqori chegara usuli usulini qo'llash orqali amalga oshiriladi Immerman-Szelepcsényi teoremasi, Geffert, Mereghetti va Pigitsziniga qarang.^[28]

Birlashtirish

• DFA: ${ displaystyle mn}$ shtatlari, Yu, Zhuang va Salomaa-ga qarang.^[19]
• NFA: o'rtasida ${ displaystyle m + n-1}$ va ${ displaystyle m + n}$ shtatlari, Xolzer va Kutribga qarang.^[20]
• 2DFA:${ displaystyle e ^ { Theta ({ sqrt {(m + n) log (m + n)}})}}$ shtatlari, qarang Kunc va Okhotin.^[23]
• 2NFA:${ displaystyle e ^ { Theta ({ sqrt {(m + n) log (m + n)}})}}$ shtatlari, qarang Kunc va Okhotin.^[23]

Kleene yulduzi

• DFA: ${ displaystyle (n-1) ^ {2} +1}$ shtatlari, Yu, Zhuang va Salomaa-ga qarang.^[19]
• NFA: ${ displaystyle n + 1}$ shtatlari, Xolzer va Kutribga qarang.^[20]
• O'FA: ${ displaystyle (n-1) ^ {2} +1}$ shtatlari, Okhotinga qarang.^[26]
• 2DFA:${ displaystyle Theta ((g (n)) ^ {2})}$ shtatlari, qarang Kunc va Okhotin.^[23]
• 2NFA:${ displaystyle Theta (g (n))}$ shtatlari, qarang Kunc va Okhotin.^[23]

Qo'shimcha o'qish

Holzer va Kutrib tomonidan yozilgan davlat murakkabligi bo'yicha so'rovlar^[36][37]va Gao va boshq.^[38]

Davlat murakkabligi bo'yicha yangi tadqiqotlar odatda yillik seminarlarda namoyish etiladiRasmiy tizimlarning tavsifiy murakkabligi (DCFS), da Avtomatlarni tatbiq etish va qo'llash bo'yicha konferentsiya (CIAA) va turli konferentsiyalarda nazariy informatika umuman.

Adabiyotlar