..., и другие задачи.

Так алгоритм Магу "сделал" теоретическую сложность этих задач ниже экспоненциальной?

? Или-таки стали вникать в суть и пошло-поехало:
кроме P и NP
P — полиномиальное время (наиболее часто используется в вычислениях, поскольку задачи этого класса могут быть решены за реальное время)
NP — для задач этого класса неизвестны эффективные алгоритмы решения, поэтому рассматриваются алгоритмы проверки правильности решений (полный перебор вариантов)

обязательно надо уточнять (, чтобы всё не выглядело ерундой)

PSPACE — полиномиальные затраты памяти
EXP — экспоненциальная временная сложность
ESPACE — экспоненциальные затраты памяти
...

Ведь оптимальное раскрытие-сокращение длиннющих многопеременных булевых выражений требует огромной памяти. И т.д. и т.п.

__________________________
__________________________
PS Что есть "алгоритм Магу" -
http://sci.sernam.ru/book_comb.php?id=31
...

ведь наверно любой средний программист (и алгоритмист) легко
переведет экспоненциальный рост времени в экспоненциальный рост памяти, "сделав" при этом рост времени вообще линейным

а есть еще массивные параллельные вычисления, где дополнительные параллельные блоки могут подключаться
по мере надобности,
а есть еще аналоговые вычислительные подмодули,
а есть еще ...

и еще что-то обязательно появится