هوش مصنوعی کامل
دشوارترین مسائل حوزه هوش مصنوعی به طور غیر رسمی با عنوان AI-Complete یا AI-Hard شناخته می‌شوند. اگر هوشمندی را محاسباتی فرض کنیم، دشواری این مسائل محاسباتی با حل مسئله اصلی هوش مصنوعی یا هوش مصنوعی قوی معادل است؛ یعنی بتوان رایانه‌ها را به اندازه انسان‌ها هوشمند کرد. اینکه یک مسئله را AI-Complete بنامیم نشان‌دهنده یک نگرش است که آن مسئله با یک الگوریتم خاص ساده حل نمی‌شود.
بر اساس فرضیه‌ای مسائل AI-Complete شامل بینایی رایانه‌ای، درک زبان طبیعی و سر و کار داشتن با شرایط غیرمنتظره در حین حل کردن هر مسئله واقعی می‌باشند.
در حال حاضر مسائل AI-Complete تنها با فناوری رایانه‌ای نوین قابل حل نیستند و نیازمند محاسبه انسان نیز می‌باشند. این ویژگی می‌تواند مفید باشد؛ به عنوان مثال برای آزمودن حضور انسان (مانند کپچاها) و در امنیت رایانه برای جلوگیری از حملات جستجوی فراگیر.
این اصطلاح توسط Fanya Montalvo به تقلید از NP-Complete و NP-Hard در نظریه پیچیدگی، که به طور رسمی معروف‌ترین گروه از مسائل دشوار را توصیف می‌کند، ابداع شد. اولین استفاده‌های این اصطلاح در مقاله دکترای سال 1987 اریک مولر و در فهرست اصطلاحات سال 1991 اریک ریموند هستند.
بر اساس فرضیه‌ای مسائل AI-Complete شامل موارد زیر می‌شوند:
برای ترجمه دقیق، ماشین باید قادر به فهمیدن متن باشد. ماشین باید بتواند بحث نویسنده را دنبال کند، بنابراین باید توانایی استدلال داشته باشد. باید دانش عام گسترده‌ای داشته باشد تا بداند که در مورد چه چیزی بحث می‌شود، حداقل باید با واقعیت‌هایی که یک انسان مترجم متوسط می‌داند آشنا باشد. بخشی از این دانش در قالب واقعیت‌هایی است که می‌توانند به طور صریح بیان شوند، اما بخشی دیگر ناخودآگاه است و به بدن انسان ارتباط دارد؛ برای مثال، ممکن است لازم باشد که ماشین چگونگی حس کردن اقیانوس را درک کند تا استعاره‌ای خاص در متن را دقیق ترجمه کند. همچنین باید اهداف، مقاصد و حالات احساسی نویسنده را الگو قرار دهد تا به طور دقیق در یک زبان جدید آن‌ها را بازسازی کند. به طور خلاصه، ماشین لازم است طیف گسترده‌ای از مهارت‌های فکری انسانی را داشته باشد؛ از جمله استدلال، دانش عام و شهود که زمینه‌ساز حرکت و تغییر دادن، درک و هوش اجتماعی است. بنابراین، اعتقاد بر این است که ترجمه ماشینی AI-Complete است؛ یعنی ممکن است به هوش مصنوعی قوی نیاز باشد تا به خوبی که انسان می‌تواند ترجمه کند، انجام پذیرد.
سیستم‌های هوش مصنوعی کنونی نسخه‌های بسیار ساده و یا محدود‌شده از مسائل AI-Complete را می‌توانند حل کنند، اما هرگز قادر به حل کردن در حالت کلی آن‌ها نیستند. وقتی محققان هوش مصنوعی برای ارتقای سیستم‌های خود تلاش می‌کنند تا شرایط واقعی و پیچیده‌تر را اداره کنند، برنامه‌ها بدون داشتن درک ابتدایی یا دانش عام از وضعیت، بیش از حد شکننده می‌شوند. زمانی که شرایط غیرمنتظره‌ی خارج از زمینه اصلی مسئله آن‌ها شروع به ظاهر شدن می‌کند، با شکست مواجه می‌شوند. انسان‌ها هنگامی که با موقعیت‌های جدید در جهان سر و کار دارد، این حقیقت که می‌دانند چه انتظاری داشته باشند بسیار به آن‌ها کمک می‌کند. آن‌ها می‌دانند همه چیزهای اطرافشان چه هستند، چرا آنجا هستند، چه کاری را ممکن است انجام دهند و غیره. آن‌ها می‌توانند شرایط غیرمعمول را تشخیص دهند و متناسب با آن تنظیم شوند. ماشینی بدون هوش مصنوعی قوی مهارت دیگری ندارد تا در مواقع اضطراری آن را جایگزین کند.
نظریه پیچیدگی محاسباتی با دشواری محاسباتی نسبی توابع محاسبه‌پذیر سر و کار دارد. بر حسب تعریف، این نظریه مسائلی که راه‌حلشان ناشناخته است یا به طور صوری مشخص نشده‌اند را در بر نمی‌گیرد. از آنجا که بسیاری از مسائل هوش مصنوعی هنوز صوری‌سازی نشده‌اند، نظریه پیچیدگی معمول تعریف AI-Complete بودن را مجاز نمی‌داند.
برای رفع این مشکل، یک نظریه پیچیدگی برای هوش مصنوعی ارائه شده است. این نظریه بر اساس مدلی است که بار محاسباتی را بین کامپیوتر و انسان تقسیم می‌کند؛ یعنی بخشی توسط رایانه و بخشی دیگر توسط انسان حل می‌شود. این امر به شکل یک ماشین تورینگ که با کمک انسان کار می‌کند صوری‌سازی شده است. این صوری‌سازی پیچیدگی الگوریتم، پیچیدگی و کاهش پذیری مسئله را تعریف می‌کند که اجازه تعریف کلاس‌های هم‌ارزی را می‌دهد.
پیچیدگی اجرای یک الگوریتم با ماشین تورینگی که به کمک انسان کار می‌کند، با دوتایی formula_1 داده می‌شود که عنصر اول نشان‌دهنده‌ی پیچیدگی قسمت انسان است و عنصر دوم پیچیدگی قسمت ماشین است.
در ادامه پیچیدگی حل چند مسئله با ماشین تورینگی که به کمک انسان کار می‌کند ذکر شده است: