OpenAI می‌گه هوش مصنوعیش فرضیهٔ زمان نمایی رو رد کرده
هوش مصنوعیClaude Opus 5.5خلاصهٔ کامل‌تر
OpenAI اعلام کرده سیستم هوش مصنوعیش اثباتی پیدا کرده که نشون می‌ده فرضیهٔ زمان نمایی (Exponential Time Hypothesis یا ETH) غلطه. به گفتهٔ OpenAI، ساخت و بررسی این اثبات حدود ۱۰ روز طول کشیده. ETH سال ۱۹۹۹ توسط Russell Impagliazzo و Ramamohan Paturi مطرح شد و می‌گه بعضی مسئله‌های سخت، مثل مسئلهٔ SAT (یعنی پیداکردن مقادیری که یه فرمول منطقی رو درست کنه)، تو بدترین حالت راهی خیلی سریع‌تر از brute force ندارن.
مقاله برای توضیح، مثال قفل رمزدار رو می‌زنه: هر رقمی که اضافه میشه، تعداد حالت‌ها ضربی زیاد میشه، نه یه‌کم. ETH می‌گفت هیچ ترفند الگوریتمی نمی‌تونه از این رشد نمایی کاملاً فرار کنه. محقق‌ها اونقدر بهش اعتماد داشتن که کلی نتیجهٔ شرطی روش ساختن، از جنس «اگه ETH درست باشه، این مسئله هم سخته». یعنی ردکردنش فقط یه جواب رو عوض نمی‌کنه، دیوار باربر کلی اثبات دیگه رو تکون می‌ده.
طبق ادعای OpenAI، مدلش روشی برای حل نسخهٔ سخت این مسئله‌ها پیدا کرده که از کفی که ETH تعیین می‌کرد سریع‌تره. این یعنی مسئله یهو سریع یا کاربردی نمی‌شه و هنوز در عمل کنده. فقط از نظر asymptotic (یعنی رفتار وقتی ورودی خیلی بزرگ میشه) از اون حد نظری بهتره، و کل یافته همین فاصله‌ست.
اثبات با Lean بررسی شده؛ Lean یه ابزار اثبات صوری هست که هر قدم منطقی رو خودکار چک می‌کنه، مثل کامپایلری که کد رو چک می‌کنه. این اعتماد رو بالا می‌بره ولی جای داوری انسانی رو نمی‌گیره. OpenAI سراغ Ryan Williams، از نظریه‌پردازهای شناخته‌شدهٔ پیچیدگی، رفته و اون یه گروه بررسی تشکیل داده که خود Impagliazzo و Paturi هم توشن.
مقاله تأکید می‌کنه این یعنی P برابر NP نیست. ETH یه فرض قوی‌تر و مشخص‌تر از «P با NP برابر نیست» هست و ردکردنش اون سؤال رو حل نمی‌کنه. Greg Brockman، رئیس OpenAI، هم گفته P احتمالاً هنوز با NP برابر نیست. پس رمزنگاری و امنیت بانکداری آنلاین هم از این نتیجه آسیبی نمی‌بینن.
به گفتهٔ نویسنده، مسئله‌هایی مثل مسیریابی کامیون‌ها، زمان‌بندی، چیدمان مدار روی تراشه و برنامه‌ریزی فرودگاه‌ها از همین خانواده‌ان. پیشرفت نظری فوراً چیزی رو عوض نمی‌کنه، ولی ممکنه سال‌ها بعد به الگوریتم‌های بهتر و ارزون‌تر برسه. واکنش‌ها هم دوگانه بوده: بعضی اونو شاید بزرگ‌ترین غافلگیری بیست سال اخیر نظریهٔ پیچیدگی می‌دونن، بعضی هم یادآوری می‌کنن که نتیجه‌های این مرز معمولاً شکننده‌ان.
نکات کلیدی:
- ETH سال ۱۹۹۹ توسط Impagliazzo و Paturi مطرح شد و حدود ۲۷ سال پایهٔ کلی نتیجه تو نظریهٔ پیچیدگی بوده.
- به گفتهٔ OpenAI، اثبات حدود ۱۰ روزه ساخته و بررسی شده.
- اثبات با ابزار Lean صوری بررسی شده ولی هنوز داوری انسانی کامل نشده.
- Ryan Williams به‌همراه Impagliazzo و Paturi دارن ادعا رو بررسی می‌کنن.
- این نتیجه P در برابر NP رو حل نمی‌کنه و رمزنگاری فعلی رو تهدید نمی‌کنه.
- مسیریابی، زمان‌بندی و طراحی تراشه از همین خانوادهٔ مسئله‌ها هستن.
