دشوارترین مسائل حوزه هوش مصنوعی به طور غیر رسمی با عنوان AI-Complete یا AI-Hard شناخته می‌شوند. اگر هوشمندی را محاسباتی فرض کنیم، دشواری این مسائل محاسباتی با حل مسئله اصلی هوش مصنوعی یا معادل است؛ یعنی بتوان رایانه‌ها را به اندازه انسان‌ها هوشمند کرد. اینکه یک مسئله را AI-Complete بنامیم نشان‌دهنده یک نگرش است که آن مسئله با یک الگوریتم خاص ساده حل نمی‌شود.
 بر اساس فرضیه‌ای مسائل AI-Complete شامل ، و سر و کار داشتن با شرایط غیرمنتظره در حین حل کردن هر مسئله واقعی می‌باشند. 
 در حال حاضر مسائل AI-Complete تنها با فناوری رایانه‌ای نوین قابل حل نیستند و نیازمند نیز می‌باشند. این ویژگی می‌تواند مفید باشد؛ به عنوان مثال برای آزمودن حضور انسان (مانند ها) و در برای جلوگیری از . 
 این اصطلاح توسط به تقلید از و در ، که به طور رسمی معروف‌ترین گروه از مسائل دشوار را توصیف می‌کند، ابداع شد. اولین استفاده‌های این اصطلاح در مقاله دکترای سال 1987 اریک مولر و در سال 1991 هستند. 
 بر اساس فرضیه‌ای مسائل AI-Complete شامل موارد زیر می‌شوند:
 
 
 
 
 مقالهٔ اصلی: برای ترجمه دقیق، ماشین باید قادر به فهمیدن متن باشد. ماشین باید بتواند بحث نویسنده را دنبال کند، بنابراین باید توانایی داشته باشد. باید گسترده‌ای داشته باشد تا بداند که در مورد چه چیزی بحث می‌شود، حداقل باید با واقعیت‌هایی که یک انسان مترجم متوسط می‌داند آشنا باشد. بخشی از این دانش در قالب واقعیت‌هایی است که می‌توانند به طور صریح بیان شوند، اما بخشی دیگر ناخودآگاه است و به بدن انسان ارتباط دارد؛ برای مثال، ممکن است لازم باشد که ماشین چگونگی حس کردن اقیانوس را درک کند تا استعاره‌ای خاص در متن را دقیق ترجمه کند. همچنین باید اهداف، مقاصد و حالات احساسی نویسنده را الگو قرار دهد تا به طور دقیق در یک زبان جدید آن‌ها را بازسازی کند. به طور خلاصه، ماشین لازم است طیف گسترده‌ای از مهارت‌های فکری انسانی را داشته باشد؛ از جمله ، و شهود که زمینه‌ساز ، و است. بنابراین، اعتقاد بر این است که AI-Complete است؛ یعنی ممکن است به هوش مصنوعی قوی نیاز باشد تا به خوبی که انسان می‌تواند ترجمه کند، انجام پذیرد.
 مقالهٔ اصلی: سیستم‌های هوش مصنوعی کنونی نسخه‌های بسیار ساده و یا محدود‌شده از مسائل AI-Complete را می‌توانند حل کنند، اما هرگز قادر به حل کردن در حالت کلی آن‌ها نیستند. وقتی محققان هوش مصنوعی برای ارتقای سیستم‌های خود تلاش می‌کنند تا شرایط واقعی و پیچیده‌تر را اداره کنند، برنامه‌ها بدون داشتن درک ابتدایی یا از وضعیت، بیش از حد می‌شوند. زمانی که شرایط غیرمنتظره‌ی خارج از زمینه اصلی مسئله آن‌ها شروع به ظاهر شدن می‌کند، با شکست مواجه می‌شوند. انسان‌ها هنگامی که با موقعیت‌های جدید در جهان سر و کار دارد، این حقیقت که می‌دانند چه انتظاری داشته باشند بسیار به آن‌ها کمک می‌کند. آن‌ها می‌دانند همه چیزهای اطرافشان چه هستند، چرا آنجا هستند، چه کاری را ممکن است انجام دهند و غیره. آن‌ها می‌توانند شرایط غیرمعمول را تشخیص دهند و متناسب با آن تنظیم شوند. ماشینی بدون هوش مصنوعی قوی مهارت دیگری ندارد تا در مواقع اضطراری آن را جایگزین کند. 
 با دشواری محاسباتی نسبی سر و کار دارد. بر حسب تعریف، این نظریه مسائلی که راه‌حلشان ناشناخته است یا به طور صوری مشخص نشده‌اند را در بر نمی‌گیرد. از آنجا که بسیاری از مسائل هوش مصنوعی هنوز صوری‌سازی نشده‌اند، نظریه پیچیدگی معمول تعریف AI-Complete بودن را مجاز نمی‌داند.
 برای رفع این مشکل، یک نظریه پیچیدگی برای هوش مصنوعی ارائه شده است. این نظریه بر اساس است که بار محاسباتی را بین کامپیوتر و انسان تقسیم می‌کند؛ یعنی بخشی توسط رایانه و بخشی دیگر توسط انسان حل می‌شود. این امر به شکل یک که با کار می‌کند صوری‌سازی شده است. این صوری‌سازی پیچیدگی الگوریتم، پیچیدگی و کاهش پذیری مسئله را تعریف می‌کند که اجازه تعریف را می‌دهد.
 پیچیدگی اجرای یک الگوریتم با ماشین تورینگی که به کمک انسان کار می‌کند، با دوتایی داده می‌شود که عنصر اول نشان‌دهنده‌ی پیچیدگی قسمت انسان است و عنصر دوم پیچیدگی قسمت ماشین است.
 در ادامه پیچیدگی حل چند مسئله با ماشین تورینگی که به کمک انسان کار می‌کند ذکر شده است:
{"title": "هوش مصنوعی کامل", "link": "https://fa.wikipedia.org//w/index.php?title=%D9%87%D9%88%D8%B4_%D9%85%D8%B5%D9%86%D9%88%D8%B9%DB%8C_%DA%A9%D8%A7%D9%85%D9%84&oldid=33292363", "language": "fa"}