تقلیلپذیری و درجات حلناپذیری
تقلیلپذیری دشواری مسائل را با تبدیل یکی به دیگری مقایسه میکند و گروهبندی مسائل با دشواری یکسان، درجات حلناپذیری را ایجاد میکند که ساختار جهان فراتر از محاسباتی را شکل میدهد.
Definition
یک مسئله زمانی به مسئله دیگری تقلیل مییابد که الگوریتمی با دسترسی به حلکننده برای دومی بتواند اولی را حل کند؛ مسائلی که به یکدیگر تقلیل مییابند، درجه حلناپذیری مشترکی دارند و این درجات یک ترتیب را تشکیل میدهند که دشواری الگوریتمی نسبی را اندازهگیری میکند.
Scope
این موضوع شامل تقلیلپذیری یکبهیک و تورینگ، استفاده از تقلیلها برای اثبات حلناپذیری، عملیات پرش تورینگ که مسائل ذاتاً دشوارتری را تولید میکند، سلسلهمراتب حسابی که مسائل را بر اساس پیچیدگی منطقی طبقهبندی میکند، و نتایج اصلی نظریه درجه مانند وجود درجات میانی است.
Core questions
- چگونه میتوانیم بگوییم یک مسئله حلناپذیر دشوارتر از دیگری است؟
- چگونه از تقلیلها هم برای اثبات حلناپذیری و هم برای سازماندهی مسائل استفاده میشود؟
- پرش تورینگ چه چیزی را تولید میکند و چرا همیشه ذاتاً دشوارتر است؟
- آیا مسائلی وجود دارند که دقیقاً بین مسائل تصمیمپذیر و مسئله توقف قرار گیرند؟
Key theories
- تقلیلپذیری و پرش تورینگ
- تقلیلپذیری تورینگ مسائل را از طریق محاسبات اوراکل به هم مرتبط میکند و پرش یک مسئله، که توقف را نسبت به آن کدگذاری میکند، همیشه ذاتاً دشوارتر است و یک برج بیپایان از مسائل دشوارتر و دشوارتر را ایجاد میکند.
- وجود درجات میانی
- قضیه فریدبرگ-موچنیک با ساخت مسائل شمارشپذیر محاسباتی که حلناپذیر هستند اما ذاتاً آسانتر از مسئله توقف هستند، با استفاده از روش اولویت، مسئله پست را حل کرد و نشان داد که درجات ساختار غنی دارند.
Clinical relevance
تکنیک تقلیل، ابزار روزمره برای اثبات حلناپذیری مسائل یا، در نظریه پیچیدگی، اثبات دشواری آنها است: نشان دادن اینکه یک مسئله دشوار شناختهشده به یک مسئله جدید تقلیل مییابد، دشواری را منتقل میکند، که دقیقاً همان روشی است که نتایج حلناپذیری و NP-کامل بودن در سراسر ریاضیات و علوم کامپیوتر اثبات میشوند.
History
تورینگ در سال ۱۹۳۹ ماشینهای اوراکل را معرفی کرد و پست در سال ۱۹۴۴ مطالعه درجات حلناپذیری را چارچوببندی کرد و مسئله وجود درجات میانی شمارشپذیر محاسباتی را مطرح نمود. فریدبرگ و موچنیک به طور مستقل در سالهای ۱۹۵۶–۱۹۵۷ با ابداع روش اولویت، که به یک تکنیک اصلی در این زمینه تبدیل شد، آن را حل کردند.
Key figures
- Emil Post
- Alan Turing
- Richard Friedberg
- Albert Muchnik
Related topics
Seminal works
- soare2016
- rogers1987
Frequently asked questions
- تقلیل به طور شهودی چیست؟
- روشی برای حل یک مسئله با استفاده از حلکننده برای مسئله دیگر است. اگر بتوانید هر نمونهای از مسئله A را به نمونهای از مسئله B ترجمه کنید به طوری که پاسخها مطابقت داشته باشند، آنگاه B حداقل به اندازه A دشوار است و راهحل B منجر به راهحل A میشود.
- آیا مسائلی دشوارتر از مسئله توقف وجود دارند؟
- بله، بینهایت مسئله. اعمال پرش تورینگ بر مسئله توقف، مسئلهای ذاتاً دشوارتر را به دست میدهد و تکرار این عملیات یک سلسلهمراتب بیپایان را میسازد، بنابراین حلناپذیری در درجات نامحدود و نه در یک سطح واحد وجود دارد.