بیاید در مورد مفهوم ریداکشن، یکی از پایه‌ای ترین عملیات‌ها برای حل مسئله، صحبت کنیم.
فرض کنید یه تابعی نوشتیم که اگه بهش عدد مثبتی رو بدیم، می‌تونه بگه اون عدد فرد هست یا نه. ما نیاز به حل یه مسئله داریم که اگه عدد مثبتی بهمون دادن، بگیم زوجه یا نه، چطوری این مسئله رو حل می‌کنین؟
خیلی ساده، با علم به این که هر عدد یا زوجه یا فرد، ورودی رو می‌دیم به ماشین، اگه ماشین گفت فرده، ما می‌گیم زوج نیست و اگر گفت فرد نیست می‌گیم زوجه، اگه ماشین خطا داد که ورودیت درست نیست، ما هم خطا می‌دیم که ورودی درست نیست. به زبان ساده، این می‌شه کدمون:
isEven = not . isOdd
توی این فرایند، ما مسئله زوج بودن اعداد مثبت رو reduce کردیم به مسئله فرد بودن اعداد مثبت.
حالا یه مسئله کمی پیچیده‌تر رو در نظر بگیرید، فرض کنید ماشینی داریم که می‌تونه بهمون بگه عددی به ۷ بخش‌پذیر هست یا نه، و ما می‌خوایم مسئله پیدا کردن باقی‌مانده به ۷ رو حل کنیم. می‌تونیم برای ورودی x به این صورت عمل کنیم:
آیا x بر هفت بخش‌پذیر هست؟ اگر آره خروجی صفر بده آیا x + 1 برهفت بخش‌پذیر هست؟ اگر آره خروجی یک بده آیا x + 2 بر هفت بخش‌پذیر هست؟ اگر آره خروجی دو بده …. آیا x + 5 بر هفت بخش‌پذیر هست؟ اگر آره خروجی پنج بده و اگر نه خروجی شش بده.
این بار و برای حل این مسئله ما ماشین بخش‌پذیریمون رو ۶ بار فراخوانی کردیم، ولی بالاخره تونستیم مسئله رو با استفاده از این ماشین حل کنیم. آیا راه ساده‌تری وجود نداره؟ چرا، اگر ماشینی داشتیم که می‌تونست باقی‌مانده برامون حساب کنه اصلا نیازی به این کارها نبود، ولی نکته اینه که ما لزوما دنبال بهترین راه حل نیستیم، صرفا دنبال حل مسئله با ابزارهایی که داریم تو زمان منطقی هستیم.
منظور از زمان منطقی چیه؟ اگه یادتون باشه تو این پست گفتیم که زمان حل راه‌حل رو با طول ورودی می‌سنجیم، و حالت‌های زیادی می‌تونه داشته باشه، از معروف‌ترین‌هاشون P یا کلاس خطی، که شامل چیزهایی مثل O(n)و O(n^2) روی ماشین دترمینیستیک هست. اما تو این سبک از مسائل چطوری می‌شه زمان رو سنجید وقتی درباره یک ماشین جانبی - اینجا ماشین بخش‌پذیری بر هفت - صحبت می‌کنیم؟
اگر از دید راه حلی که مسئله می‌بره نگاه کنیم، نمی‌تونیم به این سوال جواب بدیم چون در مورد پیچیدگی ماشینی که به هفت بخش‌پذیری رو می‌سنجه اطلاعاتی نداریم، اما می‌شه بیایم و از مفهوم Oracle استفاده کنیم، به این صورت که فرض کنیم یک اوراکل دانا داریم که به محض این که ازش سوال بپرسیم بهمون جواب می‌ده، با این وجود چقدر طول می‌کشه که مسئله رو حل کنیم؟ خب برای مسئله بالا O(1) تا طول می‌کشه چون صرفا ۶ بار اوراکل رو صدا زدیم و ۶ تا بخش پذیری چک کردیم.
به این نحوه تبدیل مسائل به همدیگه و نگاه کردن به پیچیدگیشون می‌گیم reduction through oracle و به جای صحبت کردن در مورد پیچیدگی کل ماشین، در مورد تبدیل کردن پیچیدگی‌ها صحبت می‌کنیم.
اما این اوراکل‌ها کجا کاربرد دارن؟ حقیقت اینه که وقتی در سطح بالاتر از صفر و یک و سخت‌افزار کد می‌نویسیم و صحبت از پیچیدگی کنیم داریم عملا از این قضیه استفاده می‌کنیم، معمولا همه instructionهای پردازنده برامون این نقش رو دارن، هر کدوم رو ما یک پیچیدگی محدود و خیلی کم می‌بینیم و به جزئیاتش توجهی نمی‌کنیم. همینطور وقتی از یک کتاب‌خونه استفاده می‌کنیم، به جزئیات پیاده سازی توجهی نمی‌کنیم و شاید حتا ندونیم چقدر قراره طول بکشه اجراش، صرفا می‌دونیم که یک اوراکل دانایی هست که اگر بهش ورودی مناسب بدیم خروجی مناسب با side effect قابل قبول می‌ده.