Разработка новых технологий необходима для моделирования различных параллельных многоагентных систем типа операций наземного и воздушного боя, отслеживания и возможного перехвата ракет и спутников, разведывательных операций наблюдения и т.д. Беспилотные самолеты или танки могут участвовать в разведывательных миссиях или в полномасштабной боевой операции. Подобные отряды интеллектуальных транспортных средств могут участвовать и на стороне противника. Управление этими действиями требует постоянной адаптации к промежуточным результатам и динамическому пересчёту в режиме реального времени.

Ещё один пример — это задача управления в режиме реального времени воздушным боем, в котором группа самолётов (пилотируемых или беспилотных), оснащённых защитными средствами, уклоняется от группы преследователей, оснащённых ракетами. Другой пример — это задача оптимального управления беспилотными самолётами (UAV), которые барражируют в разведывательном полёте, чтобы определить местонахождение подвижных пусковых установок ракет. Фактические точки запуска ракет обычно обнаруживаются датчиками при помощи спутника. UAV используются для того, чтобы, зная координаты этих точек, найти подвижные установки и, по возможности, уничтожить их. В сценарии из реальной жизни управление UAV нужно рассматривать вместе с воздушным боем, когда UAV уклоняются от преследующих их самолетов врага и, в свою очередь, продолжают поиск подвижных пусковых установок противника. Подобные задачи генерации и перепланирования боевых сценариев в режиме реального времени существенны также для морских и наземных операций.

Традиционные модели боевых операций могут быть вычисляемы и даже могут иногда иметь аналитические решения в простых случаях. Однако, в реальных ситуациях при использовании традиционных подходов эти задачи в вычислительном отношении неразрешимы.

Задачи моделирования космического боя, в общем-то, подобны другим задачам боевого моделирования. Однако, астродинамика космического корабля делает эти задачи значительно более сложными. Другой фактор — автономность транспортного средства. В то время как автономность наземных, морских и воздушных транспортных средств очень желательна, она просто необходима для космического корабля, особенно если он далеко от Земли. Моделирование и управление боем двух-трёх космических кораблей требует огромного количества вычислений. Задачи с ещё большим числом транспортных средств в вычислительном отношении неразрешимы (Шинар, 1990; Гарсия-Ортиз и др., 1993).

Другой класс задач связан с организацией работы интеллектуальных автоматов в индустриальной среде. Группы роботов перемещаются по заводу, комплектуют сборочные детали, подают их на сборочный конвейер и собирают изделие. В результате намеренно локализованного управления, роботы сотрудничают только в пределах своих групп. Различные группы конкурируют друг с другом за общие ресурсы, включая детали, пути движения, очерёдность сборки и т.д. Планирование этих действий требует огромного количества вычислений при использовании традиционных подходов.

Задачи конверсии программного обеспечения (ПО) требуют преобразования неструктурированных программ в объектно-ориентированное ПО, причём, иногда требуется, чтобы конечный результат такого преобразования был доказуемо правильной программой. Цель этой конверсии состоит в преобразовании неструктурированного оригинала, так называемого наследуемого ПО, в изделие, которое можно сопровождать (т.е. вносить в него изменения) в течение его жизненного цикла. Этот класс задач может быть сведен к задачам преобразования графа, где первоначальный граф представляет ПО, которое нужно конвертировать. Как правило, для этого используются системы переделки графов (graph-rewriting systems). В то время как ПО небольшого размера конвертируемо, попытка перейти к конверсии реального полномасштабного ПО сталкиваются с непреодолимыми вычислительными трудностями.

Задачи безопасности и целостности компьютерных сетей и проблемы кибервойны в Интернете недавно привлекли всеобщее внимание. Вопрос состоит в том, как защитить национальную компьютерную сеть от нападения миллиардов компьютерных вирусов и червей? Какие узлы и даже ветви должны быть отключены ("пожертвованы"), какие из них следует заново подключить ("оживить") путём активизации дубликатов, какие контрмеры должны быть приняты? Традиционный ответ на эту угрозу — локальная защита. Очевидно, что количество вычислений, необходимых для генерации стратегии для глобальной защиты делает эту задачу неразрешимой.

Задачи составления расписаний с распределением ресурсов встречаются повсюду. Они включают составление графика различных операций в индустриальной среде в соответствии с очередью заявок и доставку требуемых ресурсов по месту конкретной операции. Обычно, не все заявки могут быть удовлетворены из-за нехватки ресурсов, в то время как число заявок может достигать тысяч. Как выделить самые важные заявки, чтобы получить лучший график? Одна из таких задач — это задача составления графика ремонтов генерирующего оборудования электростанций. Вывод генератора в ремонт требует, чтобы он был остановлен и, следовательно, необходимо компенсировать потерю его мощности из запасов мощности на других электростанциях. Подобные задачи, как известно, в общем случае в вычислительном отношении неразрешимы (Гэри и Джонсон, 1991).

Программирование игры в шахматы — это вовсе не обязательно важная для практики, но конечно стимулирующая и трудная задача. Она особенно привлекательна потому, что в отличие от многих других задач в шахматах истинные эксперты действительно существуют — это гроссмейстеры и шахматные чемпионы. Некоторые из них способны к анализу путём самонаблюдения и сравнения своего видения с компьютерными моделями игры. Это даёт нам шанс на успешное распознавание и формализацию их подхода с возможным его использованием в других проблемных областях.