چرا مسئلهها سختاند
ترتیبِ تاربندیشدهٔ دشواری
سختی مانند جرم درون یک مسئله ذخیره نشده است. یک حالت با حسگری بازیافتنی و با حسگری دیگر ناپیداست. یک هدف با یک عملگر دستیافتنی و با عملگری دیگر ناممکن است. یک محاسبه در یک مدل حافظه جا میشود و از ظرفیت مدلی دیگر بیرون میزند.
این سخن سختی را ذهنی نمیکند. در قفلشده با توصیفی بهتر باز نمیشود و حدس نادرست برای اثباتگری ضعیف درست نمیشود. سختی رابطهای است، زیرا ادعای کامل هم کار و هم شیوهٔ رویارویی با آن را نام میبرد. واقعی است، زیرا جهان موفقیت یا شکست آن رابطه را مقید میکند.
بازنمایی در بازخورد زندگی میکند
بازنمایی عملیاتی هر چیزی است که پیامدهای برگزیدهٔ تعامل گذشته را به برآورد یا کنش بعدی میرساند. میتواند توزیع پسین، حالت مشاهدهگر، رونوشت فشرده یا نشانههای روی کاغذ باشد. ارزش آن به بزرگیاش نیست، بلکه به حفظ تمایزهایی است که کار به آنها نیاز دارد. برای گزارشهای قطعی، پسپردازش میتواند ردههای تمایزناپذیری را یکی کند، اما نمیتواند آنها را بشکافد. بنابراین گزارش ریزتر، مجموعهٔ کنشهایی را که در سراسر هر حالت سازگار پذیرفتنی میمانند بهطور ضعیف گسترش میدهد، و یک خارجقسمت میتواند این شمول را اکید کند.
قانون احتمالی مجهول را مشخص کنید و یک سیاستِ مجاز را در نظر بگیرید که بذر تصادفیاش از مجهول مستقل است. بازنماییای که بهطور علّی از حالت آغازین خود، رونوشت کامل و سازگارشونده و آن بذر ساخته میشود نمیتواند دربارهٔ مجهول بیش از آن ورودیها اطلاعات داشته باشد. پردازش میتواند شاهد را سامان دهد، فشرده کند یا دور بریزد؛ نمیتواند شاهد بیافریند. اگر دقت هدف به اطلاعات مربوط به کار بیش از اطلاعات حالت آغازین نیاز داشته باشد، کران پایین شمار دورها همچنین به سقفی مشروط برای اطلاعات هر دور نیاز دارد. برای ادعایی دربارهٔ یک کلاس کامل از سیاستها، این سقف باید برای هر سیاست و هر تاریخچهٔ مجاز بهطور یکنواخت برقرار باشد.
حالت نردهای گاوسی این وابستگی را روشن میکند. اندازهگیریهای مستقل و تکراری دقت را جمع میکنند. نویز بیشتر اندازهگیری برای رسیدن به واریانس پسین یکسان، مشاهدههای بیشتری میطلبد. این نتیجه برای حالتی نردهای و ثابت دقیق است. فیلتر کالمن پویا سادهتر نیست: همگرایی آن به دینامیک، نویز فرایند، نگاشت مشاهده و شرطهای مشاهدهپذیری نیز بستگی دارد. برای دینامیک غیرخطی پیوستهزمان، ماتریس مشاهدهپذیری جهانشمولی از نوع کالمن وجود ندارد. ساخت هرمان و کرنر از دیفرانسیل خروجیها و مشتقهای تکرارشدهٔ لی آنها در امتداد همهٔ میدانهای برداری مجاز سامانه گستره میسازد. رتبهٔ کامل برای مشاهدهپذیری ضعیف موضعی کافی است. با رتبهٔ ثابت و ناکامل و نابودگری هموار و بسته زیر کروشه، فروبنیوس برگهای پنهان موضعی به دست میدهد؛ فضای پوچ در یک نقطهٔ تکین چنین نتیجهای نمیدهد. اگر مسیرهایی با ورودی و خروجی یکسان به یکدیگر همگرا شوند، ابهام پنهان آنها آشکارپذیر است. لولهٔ ثابت ناصفر آشکارپذیری عملی است؛ لولهای وابسته به اغتشاش که با اغتشاش به صفر میرسد گونهای مقاوم است، نه آشکارپذیری مجانبی دقیق زیر اغتشاش ناصفر.
بازیابی دقیق اغلب لازم نیست. اگر همهٔ حالتهایی که آزمایشهای مجاز از هم جدا نمیکنند دستکم یک کنش پذیرفتنی مشترک داشته باشند، عامل بیآنکه حالت واقعی را بداند میتواند مقاوم عمل کند. اطلاعات فقط هنگامی به کار مربوطاند که تصمیم دستیافتنی را تغییر دهند.
مقاومت حاشیه دارد
همگرایی اسمی میگوید مشاهدهگر درون مدل طراحی خود چه میکند. مقاومت میپرسد وقتی سامانه، حسگر، اغتشاش یا خرابی با آن مدل فرق دارد، چه چیزی همچنان درست میماند. هیچ ادعای مقاومتی پیش از تصریح کلاس عدمقطعیت محیط و مدل، هنجار آن و کرانهایش کامل نیست.
فرض کنید نامساوی یکگامی خطا در سراسر آن کلاس بهطور یکنواخت برقرار باشد و ضریب انقباض مؤثرش از ضریب اسمی و سهم ناهمخوانی ساخته شود. سهم ناهمخوانی از حاشیهٔ انقباض میکاهد. وقتی ضریب از یک کوچکتر است، اغتشاش جمعی کراندار یک گواهیِ کران بالا میدهد: جملهای گذرا بهعلاوهٔ لولهای که شعاعش کران اغتشاش تقسیم بر حاشیهٔ باقیمانده است. این لوله نه کف دقت است و نه اثبات اینکه مشاهدهگری دیگر نمیتواند بهتر باشد. ناهمخوانی بیشتر این گواهی را ضعیفتر میکند.
اگر ضریب مؤثر از یک بگذرد، اثبات انقباض از دست میرود. این ثابت نمیکند که مشاهدهگر واقعاً واگرا میشود. تنها یعنی گواهی به مرز خود رسیده است. بیشینهٔ ادعایی واگرایی فقط درون مجموعه و هنجار تصریحشدهٔ ناهمخوانی معنا دارد.
سازگارسازی خرابی، آشکارسازی و جداسازی سه ادعای متفاوتاند. سازگارسازی خطا یا ایمنی را درون کران نگه میدارد. آشکارسازی باقیماندهٔ خراب را از عدمقطعیت سالم جدا میکند. جداسازی یک خرابی را از خرابیهای دیگر جدا میکند. اگر شعاع باقیماندهٔ سالم ρ باشد، در کوچکترین آستانهای که تنها از همین کران شعاع قابل گواهی است، نرم خطای بزرگتر از دو برابر ρ حاشیهای کافی و قطعی برای آشکارسازی است. گویهای نامزد باقیمانده با شعاع ρ هنگامی مجزا هستند که مراکزشان بیش از دو برابر ρ فاصله داشته باشند. اینها کرانهای کافی نرماند، نه تضمینهای احتمالی. ممکن است خرابی مهار شود ولی آشکار نشود، یا آشکار شود ولی جداسازیپذیر نباشد.
بهرهٔ بالای مشاهدهگر این مبادله را آشکار میکند. میتواند همگرایی اسمی را تندتر کند و همزمان نویز اندازهگیری را تقویت کند و لولهٔ مقاوم گواهیشده را بزرگتر سازد. سریع و دقیق دو نام برای یک نقطه از مرز عملکرد نیستند.
دانستن مسیر نمیسازد
کنشها دسترسپذیری را تولید میکنند. نقشهٔ کامل میتواند آشکار کند که هدف دستیافتنی است و جستوجو را کوتاه کند، اما دگرگونی غایبی نمیافزاید. اگر کنش مشتقشده فقط مسیرهایی را خلاصه کند که از هر حالت از پیش موجودند، برنامهها را کوتاه میکند بیآنکه مجموعهٔ دستیافتنی را بزرگ کند.
هدف دستیافتنی شاید همچنان افتی در تابع هدف بخواهد. عمق مانع کمترینِ بدترین افت در میان مسیرهای مجاز را اندازه میگیرد. این آمارهای گلوگاهی است، نه هزینهای عمومی. نه گامها را میشمارد، نه انرژی یا زمان جستوجو را اندازه میگیرد و نه احتمال گریز تصادفی را تعیین میکند.
پس جستوجو، پیمایش و امکان سه امر جدا هستند. ممکن است مسیری وجود داشته باشد اما ناشناخته بماند. ممکن است شناخته باشد اما ممنوع باشد. ممکن است مانعش صفر و طولش نجومی باشد. جمعکردن این سه زیر عنوان ناهمواری چشمانداز، مرز مربوط را پنهان میکند.
رفتار بر نحوهٔ نمایش آن مقدم است
یک معادلهٔ دیفرانسیل، ماشین خودکار، مدل فضای حالت یا جداسازی ورودی و خروجی، سامانهای را ارائه میکند. در صورتبندی رفتاری، سامانه عبارت است از دامنهٔ زمانی اعلامشده، فضای سیگنال و مجموعهٔ مسیرهای مجاز. مدلهای درونی متفاوت میتوانند رفتار مرزی یکسانی را ارائه کنند، بیآنکه برای فرایند واقعی به یک اندازه سودمند یا وفادار باشند.
اتصال متقابل، مسیرهای سازگار روی سیگنالهای مشترک را نگه میدارد، و پنهانسازی سیگنالهای درونی را با تصویرگیری حذف میکند. پنهانسازی پیش از ترکیب میتواند مسیرهای دیدنیای را بپذیرد که شاهدهای پنهان ناسازگار از آنها پشتیبانی میکنند. اگر مسیرهای محلی به ناحیههای کوچکتر محدود شوند و قطعههای سازگار چسبانش مجاز یکتایی داشته باشند، روی ساختار زمانی برگزیده معناشناسی شیفی میسازند. یک توپوس میتواند منطق حاصل را سامان دهد، اما اثبات ایمنی را فراهم نمیکند.
ایمنی یعنی هر مسیر مجاز حلقهبسته در مجموعهٔ امن بماند. برای دینامیک قطعی گسسته، روی رفتاری که از مجموعهٔ امن تولید میشود، این شرط همارز ناوردایی یکگامی پیشرو است. رفتار تهی بهطور تهیصدق امن است، پس گواهی سودمند کنترلگر همچنین به بیبنبستی یا زیستپذیری نیاز دارد.
انتزاع معمولاً چندبهیک است. شبیهسازی پیشرو تصویرهای انتزاعی معتبر مسیرهای عینی را میدهد. اجرای یک برنامهٔ انتزاعی همچنین میطلبد هر گام انتزاعی از همان حالت عینی که واقعاً به آن رسیدهایم بالا برده شود و موفقیت انتزاعی، موفقیت عینی را بازتاب دهد. هزینهها، ایمنی مسیری و موانع شاهدهای خود را میخواهند. حسگر، عملگر، محمول یا اوراکل تازه بسط است، نه بازبرچسبگذاری.
دشواری ترتیبی تاربندیشده دارد
ادعای پیچیدگی مجانبی به خانوادهای از ورودیها، کدگذاری و سنجهٔ اندازه، مدل ماشین و دسترسی، معیار موفقیت و سنجهٔ منابع نیاز دارد و دربارهٔ رشد در سراسر آن خانواده است. هزینهٔ دقیق، مانع یا زوج منبع و زیان برای یک نمونه واقعیتی در سطح همان نمونه است، نه بهخودیخود قضیهای مجانبی. بزرگی مجموعهٔ نامزدها بهتنهایی کران پایین نیست. ورودی یکگذره، ورودی بازخواندنی و حافظهٔ بیرونی سه مسئلهٔ متفاوت میسازند.
برای مدلی ثابت، زوج منبع و زیان را هنگامی دستیافتنی بخوانید که برنامهای درون همان بودجهٔ منبع و کران زیان بماند. زوجها مؤلفهبهمؤلفه مرتب میشوند و منبع و زیان کوچکتر بهتر است. ناحیه بهسمت بالا بسته است. نقاط دستیافتنی نامغلوب آن، هرگاه وجود داشته باشند، جبههٔ پارتوی محققشده را میسازند. مقادیر حدی مرز شاید فقط در بست قرار گیرند و هرگز محقق نشوند. زمان بیشتر شاید دقت بخرد. حافظهٔ بیشتر شاید جای محاسبهٔ دوباره را بگیرد. محدودیت اطلاعات یا هدف دسترسناپذیر میتواند برخی بودجههای لازم را به بینهایت بفرستد.
یک بافت مقایسه را ثابت کنید: کار مشترک، سورهای نمونه و محیط، کلاس عدمقطعیت، برنامههای مجاز، رابطها و مختصات منبع و زیان. تار پیرامونی آن، مجموعهٔ توانی فضای عملکردش با ترتیب شمول است. هر رویارویی به یک ناحیهٔ دستیافتنی در این تار نگاشته میشود. یک رویارویی دستکم به اندازهٔ دیگری دشوار است اگر ناحیهاش زیرمجموعهٔ ناحیهٔ دیگری باشد. این رابطه روی رویاروییها پیشترتیب است. پس از یکیگرفتن ناحیههای برابر، خارجقسمت فقط با تصویر نگاشت ناحیهٔ دستیافتنی همترتیب است، نه عموماً با سراسر تار پیرامونی.
این ترتیب لزوماً تام نیست. اگر هیچیک از دو ناحیه در دیگری نگنجد، رویاروییها قیاسناپذیرند. مرزهای متقاطع این حالت را آشکار میکنند: یکی ممکن است در دقت زمخت بهتر و نزدیک دقت کامل بدتر باشد. رتبهبندی نردهای به قاعدهای افزوده برای مبادلهٔ منابع با زیان نیاز دارد.
برای نگاشتی از نقاط عملکرد یک بافت به بافتی دیگر، پیشتصویر یکنوا و پادورد است و قوانین همانی و ترکیب را برمیآورد. وقتی نگاشتِ نقاط پوشا باشد شمول را بازمیتاباند، و حتی بیهیچ چیزِ بیشتر، مقایسهای ناهمگن میان مواجهههای دادهشده ممکن میکند. اما پیشتصویرِ ناحیهای تحققیافته لازم نیست خودش تحققیافته باشد؛ پس بازنمایهگذاریِ ردههای تحققیافتهٔ دشواری به بستهبودن زیر پیشتصویر نیاز دارد، و انتقالِ سازگارِ مواجههها یک شاهدِ کافی است، نه یگانه شاهد. تصویرِ مستقیمِ یک انتزاعِ چندبهیک عملی همورد و جداست و شاید ترتیب را بازنتاباند. اینجا نه توپولوژی یا خمینه داریم و نه رتبهبندی سراسری در جایی که ترجمهای برای عملکرد اعلام نشده است. باقی ساخته شده است، نه ادعا: بافتها و نگاشتهایشان به یک ردهٔ کل سرهم میشوند، نگاشتهای بازنمایهگذاریِ انتخابشده دقیقاً همان لیفتهای دکارتیِ کانونی آناند، و ترتیبِ هر بافت بهصورت تارِ استاندارد درون آن مینشیند. همهٔ اینها با ماشین بررسی شده است.
کرانهای ماشین متناهی نیاز به رابط دقیق را نشان میدهند. ماشینی که باید یکی از امکانهای متمایز فراوان را نگه دارد دستکم همان شمار حالت میخواهد. ماشینی با دو به توان s حالت، s بیت ظرفیت دارد، نه دو به توان s بیت. با فرض مبنای دستکم دو و طول ورودی مثبت، کران ضربِ ارزش مکانی کتاب در حقیقت کران نسخهبرداری با خروجی دیرهنگام است که با ثابتگرفتن یکی از عملوندها روی یک به دست میآید، نه قضیهای دربارهٔ سختی عمومی ضرب.
پیشپردازش کار را جابهجا میکند، نه اینکه آن را محو کند. ساخت نمایه، کتابخانهٔ اثبات یا سلسلهمراتب انتزاع شاید گران و پرسوجوی آن ارزان باشد. مقایسهٔ منصفانه میگوید چه کسی آن را میگیرد، آیا هزینهٔ ساختش حساب میشود و میان چند نمونه بازاستفاده میشود.
یک شکل در پسِ سه مرز
سه مرز یک شکل جبری مشترک دارند، و این شکل بررسی شده است. آنچه کنشها میتوانند به آن برسند، آنچه یک مشاهده نمیتواند از هم جدا کند، و آنچه پس از پنهانکردن یک سیگنال از رفتار میماند، همگی بستارند: دو بار بستن همان یک بار بستن است. برای همین افزودن حرکتی که همین حالا دستیافتنی است چیزی نمیافزاید و آمارهای که از گزارشی موجود حساب شود چیز تازهای را جدا نمیکند. این شکل حدهای اثباتشده هم دارد. پنهانسازی با اتصال مؤلفهها جابهجا نمیشود، و بستاری در یک بافت لازم نیست با بازنمایهگذاری به بافتی دیگر سازگار باشد؛ هر دو شکست مثالهای نقض متناهی و کوچکی دارند.
دلیلی بررسیشده هم هست که چرا دشواری ترتیب میماند و یک عدد نمیشود. فروکاستنِ ردههای دشواری به یک گروه، همان تکمیلِ گروهیِ استاندارد، همهچیز را پاک میکند: ناحیهها با اجتماع ترکیب میشوند، اجتماعْ تکرار را در خود میبلعد، و تکمیلِ چنین عملی بدیهی است. بودجههای اشباعشونده هم به همین شکل فرومیریزند. از این گذر فقط شمارشهای دقیق منابع جان به در میبرند، و مسئلههای سخت آنجا زندگی نمیکنند.
وسوسهٔ باقیمانده تاب است: دادههای چسباندنی که هیچ بازگزینشِ مؤلفهها صافشان نمیکند، مانند K-نظریهٔ تابدار. این در هر دو سو بررسی شده است. تارهای ترتیبمقدار اکیدبودن را اجباری میکنند، پس آنجا هیچ چیزِ نااسپلیتی هرگز ممکن نبود، و ارائهٔ اسپلیت قضیه بود نه انتخاب. یک مثال کوچک با تارهای متقارن تابی واقعی دارد که صافشدنی نیست. نظریهٔ تابدارِ دشواری تارهایی میخواست که بیش از ترتیب به یاد بسپارند، و ضریبهایی که از تکمیل جان به در ببرند.
رابطهای و واقعی
مرزهای اطلاعات، کنش و منابع رابطهاند، اما واقعیتهای درون آنها میتوانند عینی باشند. حالتها یا با کلاس آزمایشی جدا میشوند یا نمیشوند. هدف یا در بستار کنش است یا نیست. الگوریتم یا کران تصریحشده را برآورده میکند یا نمیکند.
نیرومندترین عینیت از ناوردایی در سراسر کلاس مقایسهای ثابت میآید. تغییر دقیق مختصات رفتار را حفظ میکند. نتایج پیچیدگی میتوانند زیر شبیهسازیهای کارآمد میان مدلهای پذیرفتهشدهٔ ماشین پایدار بمانند. تغییر کلاس مقایسه پس از دیدن پاسخ چیزی را ثابت نمیکند.
پیش از تصریح کار و رویارویی، دشواری نردهای برای مسئلهٔ برهنه وجود ندارد. آنچه اندازهپذیر است نرخ اطلاعات، لولهٔ خطا، مجموعهٔ دستیافتنی، عمق مانع، حافظه، زمان، پرسوجو و زیان تقریبی است. ناحیههای دستیافتنی آنها زیرترتیبهای جزئیِ تحققیافتهای درون تارهای پیرامونی عملکرد میسازند. پیشتصویر تارهای پیرامونی را بازنمایهگذاری میکند؛ بستهبودنِ ثابتشده زیر پیشتصویر، برای نمونه از راه انتقال سازگار رویارویی، این ساختار را به ترتیب تاربندیشدهای از ردههای تحققیافتهٔ دشواری گسترش میدهد.
Lean پیامدهای متناهی و جبری مورد استفادهٔ کتاب کامل را وارسی میکند: پالایش قطعی گزارش و زیان تصمیم، حساب بودجهٔ اطلاعات، روابط بازگشتی نردهای خطا با ضریب ثابت و ضریب متغیرِ یکنواختاً کراندار، حاشیههای قطعی خطا، اشتراک ردههای مشاهده و کاوش فعال، دسترسپذیری، موانع، ناوردایی مختصات، بالابری انتزاع، کرانهای حافظهٔ متناهی، و بهینهها در پوشهای متناهی برنامه. دربارهٔ خودِ ترتیبِ تاربندیشده اکنون اینها را هم وارسی میکند: ردهٔ کل بر بافتهای مقایسه با لیفتهای دکارتی و تارهای استانداردش، عملگرهای بستار برای مرزهای کنش و اطلاعات و رفتار همراه با دو موردِ شکستِ اثباتشدهشان، و بدیهیبودنِ تکمیلِ گروهی برای ردههای دشواریِ خودتوان و بودجههای اشباعشونده. وارسی، مشتقشدن نتیجه از فرضها را ثابت میکند؛ ثابت نمیکند که فرضها مدل درست یک سیستم فیزیکیاند.