Сложности второго рода были связаны с неразрешимостью многих проблем, решение которых пытались найти с помощью искусственного интеллекта. В большинстве ранних программ искусственного интеллекта решение задач осуществлялось по принципу проверки различных комбинаций возможных шагов, которая проводилась до тех пор, пока не будет найдено решение. На первых порах такая стратегия приводила к успеху, поскольку микромиры содержали очень небольшое количество объектов, поэтому предусматривали лишь незначительный перечень возможных действий и позволяли находить очень короткие последовательности решения. До того как была разработана теория вычислительной сложности, было широко распространено такое мнение, что для "масштабирования" задач до уровня более крупных проблем достаточно просто применить более быстродействующие аппаратные средства с большим объемом памяти. Например, оптимизм, с которым были встречены сообщения о разработке метода доказательства теорем с помощью резолюции, быстро угас, когда исследователи не смогли доказать таким образом теоремы, которые включали чуть больше нескольких десятков фактов. Как оказалось, то, что программа может найти решение в принципе, не означает, что эта программа действительно содержит все механизмы, позволяющие найти данное решение на практике.

Иллюзия неограниченной вычислительной мощи распространялась не только на программы решения задач. Ранние эксперименты в области эволюции машин (которая теперь известна под названием разработка генетических алгоритмов) [502], [503] были основаны на уверенности в том, что внесение соответствующего ряда небольших изменений в машинный код программы позволяет создать программу решения любой конкретной простой задачи, обладающую высокой производительностью. Безусловно, что сам этот подход является вполне обоснованным. Поэтому общая идея состояла в том, что необходимо проверять случайные мутации (изменения в коде) с помощью процесса отбора для сохранения мутаций, которые кажутся полезными. На эти эксперименты было потрачено тысячи часов процессорного времени, но никаких признаков прогресса не было обнаружено. В современных генетических алгоритмах используются лучшие способы представления, которые показывают более успешные результаты.