NL (murakkablik) - NL (complexity)

Kompyuter fanida hal qilinmagan muammo: ${ displaystyle { mathsf {L { overset {?} {=}} NL}}}$ (kompyuter fanida hal qilinmagan muammolar)

Yilda hisoblash murakkabligi nazariyasi, NL (Nondeterministik Logaritmik-bo'shliq) bu murakkablik sinfi o'z ichiga olgan qaror bilan bog'liq muammolar a tomonidan hal qilinishi mumkin noan'anaviy Turing mashinasi yordamida logaritmik miqdori xotira maydoni.

NL ning umumlashtirilishi L, a bo'yicha logspace muammolari sinfi deterministik Turing mashinasi. Har qanday deterministik Turing mashinasi ham a noan'anaviy Turing mashinasi, bizda shunday L tarkibida mavjud NL.

NL hisoblash manbai bo'yicha rasmiy ravishda belgilanishi mumkin noan'anaviy bo'shliq (yoki NSPACE) kabi NL = NSPACE(log n).

Murakkablik nazariyasidagi muhim natijalar ushbu murakkablik sinfini boshqa sinflar bilan bog'lashga imkon beradi, bu esa jalb qilingan resurslarning nisbiy kuchi haqida aytib beradi. Sohasidagi natijalar algoritmlar, boshqa tomondan, ushbu resurs bilan qaysi muammolarni hal qilish mumkinligini aytib bering. Ko'pgina murakkabliklar nazariyasi singari, ko'plab muhim savollar NL hali ham ochiq (qarang Informatikaning hal qilinmagan muammolari ).

Ba'zan NL deb nomlanadi RL tufayli ehtimollik ta'rifi quyida; ammo, bu nom tez-tez murojaat qilish uchun ishlatiladi tasodifiy logaritmik bo'shliq, tenglashishi ma'lum emas NL.

To'liq muammolar

Bir nechta muammolar ma'lum To'liq emas ostida bo'shliqni qisqartirish, shu jumladan ST-ulanish va 2-qoniqish. ST-ulanish tugunlarni so'raydi S va T a yo'naltirilgan grafik yo'qmi T bu erishish mumkin dan S. 2-qoniqish deb so'raydi, uning har bir bandi bo'lgan formula berilgan ajratish formulani to'g'ri bajaradigan o'zgaruvchan topshiriq bo'lsa, ikkita literaldan. Masalan, qaerda ${ displaystyle neg}$ bildiradi emas, bo'lishi mumkin:

${ displaystyle (x_ {1} vee neg x_ {3}) wedge ( neg x_ {2} vee x_ ​​{3}) wedge ( neg x_ {1} vee neg x_ {2} )}$

Konteynerlar

Ma'lumki NL tarkibida mavjud P, chunki u erda polinom-vaqt algoritmi uchun 2-qoniqish, ammo yo'qligi ma'lum emas NL = P yoki yo'qmi L = NL. Ma'lumki NL = birgalikda NL, qayerda CO-NL bu tillar sinfi qo'shimchalar ichida NL. Bu natija ( Immerman-Szelepcsényi teoremasi ) tomonidan mustaqil ravishda kashf etilgan Nil Immerman va Róbert Szelepcsényi 1987 yilda; ular 1995 yilni oldilar Gödel mukofoti bu ish uchun.

Yilda elektronning murakkabligi, NL ichida joylashtirilishi mumkin Bosimining ko'tarilishi ierarxiya. Papadimitriou 1994 yilda, 16.1-sonli teorema, bizda:

${ displaystyle { mathsf {NC_ {1} subseteq L subseteq NL subseteq NC_ {2}}}}$.

Aniqrog'i, NL tarkibida mavjud AC¹. Ma'lumki NL ga teng ZPL, tasodifiy algoritmlar yordamida logaritmik fazoda va cheksiz vaqt ichida echilishi mumkin bo'lgan muammolar klassi. Biroq, u ma'lum emas yoki unga teng deb ishonilmaydi RLP yoki ZPLP, ning polinom-vaqt cheklovlari RL va ZPL ba'zi mualliflar buni nazarda tutadi RL va ZPL.

Biz bog'lashimiz mumkin NL yordamida deterministik makonga Savitch teoremasi, bu bizga har qanday nondeterministik algoritmni kvadratik jihatdan ko'proq bo'shliqda deterministik mashina tomonidan simulyatsiya qilish mumkinligini aytadi. Savitch teoremasidan biz to'g'ridan-to'g'ri quyidagilarga egamiz:

${ displaystyle { mathsf {NL subseteq SPACE}} ( log ^ {2} n) { text {teng,}} { mathsf {NL subseteq L}} ^ {2}.}$

Bu 1994 yilda ma'lum bo'lgan eng kuchli deterministik-kosmik inklyuziya edi (Papadimitriou 1994 yil 16.4.10-sonli muammo, "Simmetrik bo'shliq"). Kattaroq kosmik sinflarga kvadratik o'sish ta'sir qilmagani uchun, nondeterministik va deterministik sinflar teng ekanligi ma'lum, shuning uchun bizda PSPACE = NPSPACE.

Muqobil ta'riflar

Ehtimoliy ta'rif

Aytaylik C bo'ladi murakkablik sinfi ning qaror bilan bog'liq muammolar bilan logaritmik fazada hal etiladigan ehtimoliy Turing mashinalari hech qachon noto'g'ri qabul qilmaydigan, ammo 1/3 qismidan kamrog'ini rad etishga yo'l qo'yadigan; bu deyiladi bir tomonlama xato. Doimiy 1/3 ixtiyoriy; har qanday x 0 with bilan x <1/2 kifoya qiladi.

Aniqlanishicha C = NL. E'tibor bering C, uning deterministik hamkasbidan farqli o'laroq L, polinom vaqti bilan cheklanmaydi, chunki u polinom konfiguratsiyasiga ega bo'lsa-da, cheksiz pastadirdan qochish uchun tasodifiylikni ishlatishi mumkin. Agar biz uni polinomiya vaqti bilan cheklasak, biz sinfni olamiz RLtarkibiga kiradi, lekin ma'lum emas yoki teng deb hisoblanadi NL.

Buni aniqlaydigan oddiy algoritm mavjud C = NL. Shubhasiz C tarkibida mavjud NL, beri:

• Agar mag'lubiyat tilda bo'lmasa, ikkalasi ham barcha hisoblash yo'llarida rad etadi.
• Agar mag'lubiyat tilda bo'lsa, an NL algoritm kamida bitta hisoblash yo'li bilan qabul qiladi va a C algoritm hisoblash yo'llarining kamida uchdan ikki qismi bo'ylab qabul qiladi.

Buni ko'rsatish uchun NL tarkibida mavjud C, biz shunchaki NL algoritmi va uzunligini tasodifiy hisoblash yo'lini tanlang nva buni bajaring 2ⁿ marta. Chunki hech qanday hisoblash yo'li uzunlikdan oshmaydi nva chunki 2 borⁿ Umuman olganda hisoblash yo'llari, biz qabul qiluvchini urish uchun yaxshi imkoniyatga egamiz (quyida doimiy bilan chegaralangan).

Yagona muammo shundaki, bizda 2 ga ko'tariladigan ikkilik hisoblagich uchun log maydonida joy yo'qⁿ. Buning atrofida biz uni a bilan almashtiramiz tasodifiy oddiygina aylanadigan hisoblagich n tangalar va agar ularning hammasi boshga tushsa, to'xtaydi va rad etadi. Ushbu hodisaning ehtimoli 2 bo'lganligi sababli^.N, biz kutmoq 2. olishⁿ to'xtashdan oldin o'rtacha qadamlar. U faqat ko'rgan ketma-ket boshlarning umumiy sonini saqlab turishi kerak va ularni log maydonida hisoblashi mumkin.

Tufayli Immerman-Szelepcsényi teoremasi, unga ko'ra NL komplektlar ostida yopiladi, bu ehtimollik hisob-kitoblaridagi bir tomonlama xato nol qirrali xato bilan almashtirilishi mumkin. Ya'ni, bu muammolarni logaritmik bo'shliqdan foydalanadigan va hech qachon xato qilmaydigan probabilistik Turing mashinalari hal qilishi mumkin. Mashinadan faqat polinom vaqtidan foydalanishni talab qiladigan mos keladigan murakkablik sinfi deyiladi ZPLP.

Shunday qilib, biz faqat kosmosga qarasak, tasodifiylik va nondeterminizm bir xil darajada kuchli ekan.

Sertifikat ta'rifi

NL bilan tenglashtirilishi mumkin sertifikatlar, kabi sinflarga o'xshash NP. Faqat o'qish uchun bir marta o'qiladigan qo'shimcha lentaga ega bo'lgan deterministik logaritmik bo'shliq bilan cheklangan Turing mashinasini ko'rib chiqing. Til mavjud NL va agar shunday Turing mashinasi qo'shimcha kirish lentasida tegishli sertifikat tanlovi uchun tilda biron bir so'zni qabul qilsa va sertifikatda qat'i nazar, tilda bo'lmagan har qanday so'zni rad etsa.^[1]

Ta'riflovchi murakkablik

Ning oddiy mantiqiy tavsifi mavjud NL: unda aniq ifodalangan tillar mavjud birinchi darajali mantiq qo'shilgan bilan o'tish davri yopilishi operator.

Yopish xususiyatlari

NL klassi operatsiyalarni to'ldirish, birlashtirish va shuning uchun kesishish, birlashtirish va Kleen yulduzi ostida yopiladi.

Izohlar

Adabiyotlar

• Murakkablik hayvonot bog'i: NL
• Papadimitriou, C. (1994). "16-bob: Logaritmik fazo". Hisoblash murakkabligi. Addison-Uesli. ISBN  0-201-53082-1.
• Maykl Sipser (1997 yil 27-iyun). "8.4-8.6 bo'limlari: L va NL sinflari, NL-to'liqligi, NL coNL-ga teng". Hisoblash nazariyasiga kirish. PWS nashriyoti. pp.294–302. ISBN  0-534-94728-X.
• Murakkablik nazariyasiga kirish: 7-ma'ruza. Oded Goldreich. Taklif 6.1. Bizning C Goldreich badRSPACE (log n) deb ataydi.