Задачи не попадающие ни в класс P, ни в класс E

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

К этому классу относятся следующие задачи [20, с. 207]:

· задача о выполнимости: существует ли для данной булевской формулы, находящейся в КНФ, такое распределение истинностных значений, что она имеет значение И?

· задача коммивояжера;

· решение систем уравнений с целыми переменными;

· составление расписаний, учитывающих определенные условия;

· размещение обслуживающих центров (телефон, телевидение, срочные службы) для максимального числа клиентов при минимальном числе центров;

· оптимальная загрузка емкости (рюкзак, поезд, корабль, самолёт) при наименьшей стоимости;

· оптимальный раскрой (бумага, картон, стальной прокат, отливки), оптимизация маршрутов в воздушном пространстве, инвестиций, станочного парка;

· задача распознавания простого числа; самый лучший в настоящее время тест на простоту имеет сложность порядка O(L(n)^L(L(L(n)))), где L(n) - количество цифр в числе n (выражение L(L(L(n))) стремиться к бесконечности очень медленно; первое число, для которого L(L(L(n))) = 2, равно 10^999999999) [5, стр. 102].