WikiDer > Resurs bilan chegaralangan o'lchov

Lyutsning resurslari bilan chegaralangan o'lchov ning umumlashtirilishi Lebesg o'lchovi ga murakkablik sinflari. Dastlab u tomonidan ishlab chiqilgan Jek Lyuts. Xuddi Lebesgue o'lchovi kichik to'plamlarning hajmini aniqlash usulini beradi Evklid fazosi ${ displaystyle mathbb {R} ^ {n}}$, resurs bilan chegaralangan o'lchov murakkablik sinflarining kichik to'plamlari hajmini tasniflash usulini beradi.

Masalan, kompyuter olimlari odatda murakkablik sinfiga ishonishadi P (barchasi to'plami) qaror bilan bog'liq muammolar hal etiladigan polinom vaqti) murakkablik sinfiga teng emas NP (polinom vaqtida tekshirilishi mumkin bo'lgan, lekin hal qilinishi shart bo'lmagan barcha qarorlar to'plami). P a bo'lganligi sababli kichik to'plam NP, demak, NP P ga qaraganda ko'proq muammolarni o'z ichiga oladi. "P NP emas"- bu" NPda p-o'lchov yo'q 0 "iborasi. Bu erda p-o'lchov Lebesg o'lchovining murakkablik sinfining kichik to'plamlariga umumlashtirilishi. E, unda P mavjud. P ning p-o'lchovi 0 ga ega ekanligi ma'lum va shuning uchun "NPda p-o'lchovi yo'q 0" gipotezasi nafaqat NP va P ning teng emasligini, balki NP ning a da ekanligini anglatadi. o'lchov-nazariy ma'no, "P dan kattaroq".

Ta'rif

${ displaystyle {0,1 } ^ { infty}}$ barchaning to'plamidir cheksiz, ikkilik ketma-ketliklar. Biz ko'rishimiz mumkin haqiqiy raqam ichida birlik oralig'i cheksiz ikkilik ketma-ketlik sifatida, uni hisobga olgan holda ikkilik kengayish. Shuningdek, biz a til (ikkilik to'plam torlar) ni o'rnatib, cheksiz ikkilik ketma-ketlik sifatida nth bit ketma-ketlikni 1 ga va agar shunday bo'lsa nikkilik qator (in.) leksikografik tartib) tilda mavjud. Shunday qilib, birlik oralig'i va murakkablik sinflaridagi haqiqiy sonlar to'plami (ular tillar to'plami) ikkalasini ham cheksiz ikkilik ketma-ketliklar to'plami va shuning uchun o'lchov nazariyasi haqiqiy sonlar to'plamlari hajmini o'lchash uchun ishlatiladigan murakkablik sinflarini o'lchash uchun qo'llanilishi mumkin. Ammo, har bir hisoblanadigan murakkablik sinfida faqat a mavjud hisoblanadigan elementlarning soni (chunki hisoblash mumkin bo'lgan tillar soni) har bir murakkablik sinfiga ega Lebesg o'lchovi 0. Shunday qilib, murakkablik sinflari ichida o'lchov nazariyasini bajarish uchun biz alternativani belgilashimiz kerak o'lchov cheksiz ketma-ketlikning hisoblanadigan to'plamlarida mazmunli ishlaydi. Ushbu chora mazmunli bo'lishi uchun u har bir murakkablik sinfining asosiy ta'rifi haqida bir narsani aks ettirishi kerak; ya'ni, ular tomonidan belgilanadi hisoblash muammolari bu ma'lum bir manbaga bog'liq holda hal qilinishi mumkin.

Resurs bilan chegaralangan o'lchovning asosi Villning formulasi martingalalar. A martingale funktsiya ${ displaystyle d: {0,1 } ^ {*} dan [0, infty)}$ Shunday qilib, barcha cheklangan satrlar uchun w,

${ displaystyle d (w) = { frac {d (w0) + d (w1)} {2}}}$.

(Bu Villning martingale haqidagi asl ta'rifi, keyinchalik kengaytirilgan Jozef Leo Doob.) Martingale d deyiladi muvaffaqiyatga erishish ketma-ketlikda ${ displaystyle S in {0,1 } ^ { infty}}$ agar ${ displaystyle limsup _ {n to infty} d (S upharpoonright n) = infty,}$ qayerda ${ displaystyle S upharpoonright n}$ birinchi n bit S. Martingale muvaffaqiyatli bo'ladi ketma-ketliklar to'plamida ${ displaystyle X subseteq {0,1 } ^ { infty}}$ agar u har bir ketma-ketlikda muvaffaqiyat qozonsa X.

Intuitiv ravishda martingale - bu cheklangan miqdordagi pul bilan (masalan, bir dollar) boshlanadigan qimorboz. U bitlarning ketma-ketligini cheksiz o'qiydi. Sonli prefiksni o'qigandan so'ng ${ displaystyle w in {0,1 } ^ {*}}$, u joriy pulning bir qismiga keyingi bit 0 ga, qolgan pul esa keyingi bitga 1 bo'lishiga garov qo'yadi. Keyingi paydo bo'lgan bitga pul qo'yilgan pulni ikki baravar oshiradi va pulni yo'qotadi. paydo bo'lmagan bitga joylashtirilgan. U o'z pulining hammasiga pul tikishi kerak, ammo pulning yarmini har bir bitga qo'yib, "hech narsaga pul tikmasligi" mumkin. Martingale uchun d, d(w) pul miqdorini anglatadi d satrni o'qigandan keyin ega w. Martingalaning ta'rifi martingalada o'yinning cheklanganligi sababli qanday garovlar qo'yilishini hisoblashdan ko'ra, qancha pul bo'lishini hisoblab chiqishiga qaramay, qadriyatlarni bilib oling. d(w), d(w0) va d(w1) garovlarni hisoblash kifoya d qatorni ko'rgandan keyin 0 va 1 ga qo'yilgan w. Martingale shu paytgacha ko'rilgan satrni kirish sifatida qabul qiladigan funktsiya ekanligi, qo'yilgan garovlar faqat o'qilgan bitlarning funktsiyasi ekanligini anglatadi; garovga boshqa hech qanday ma'lumot ta'sir qilishi mumkin emas (boshqa ma'lumotlar shunday ataladi) filtrlash ichida martingalalarning umumlashtirilgan nazariyasi).

Martillarga nisbatan o'lchov bilan bog'liq asosiy natija - Villning to'plamni kuzatishidir ${ displaystyle X subseteq {0,1 } ^ { infty}}$ Lebesgue o'lchovi 0, agar faqat martingale bo'lsa, u muvaffaqiyatli bo'ladi X. Shunday qilib, biz 0 o'lchovini to'plamning barcha elementlarida muvaffaqiyat qozonadigan martingale mavjud bo'lgan o'lchov sifatida belgilashimiz mumkin.

Ushbu turdagi o'lchovlarni murakkablik sinflariga etkazish uchun Lutz martingalening hisoblash kuchini cheklashni o'ylab topdi. Masalan, har qanday martingalaga ruxsat berish o'rniga, biz undan martingale bo'lishini talab qilamiz polinom-vaqt hisoblash mumkin, keyin biz p-o'lchov ta'rifini olamiz: ketma-ketliklar to'plami p-o'lchov 0 ga ega bo'lsa, 0 ga ega hisoblash uchun polinom-vaqt to'plamda muvaffaqiyat qozonadigan martingale. Agar uning komplementida p-o'lchovi 0 bo'lsa, biz p-o'lchov 1 ga ega bo'lgan to'plamni aniqlaymiz, masalan, NP ning p-o'lchovi 0 ga ega emasligini yuqorida aytib o'tilgan taxminni isbotlash, hech qanday polinom-vaqt martingali muvaffaqiyatga erishmasligini isbotlashga teng barcha NP.

Deyarli to'liq

Muammo shundaki deyarli to'liq a murakkablik sinfi C, agar u C bo'lsa va C dagi "ko'p" muammolar unga kamayadi. Aniqrog'i, muammoning kamayishiga olib keladigan S muammolari to'plami, o'lchov manbalari bo'yicha bir to'plamdir. Bu muammodan ko'ra zaifroq talab to'liq sinf uchun.

Adabiyotlar

• van Melkebek, Diter (2001), Hisoblash murakkabligidagi tasodifiylik va to'liqlik, Springer, ISBN 3-540-41492-4, dan arxivlangan asl nusxasi 2011-07-19

Tashqi havolalar

• Resurslarga asoslangan o'lchovlar bibliografiyasi