Алгоритм Магу и задачи: о нахождении клики, о расстановке ферзей, о минимальной раскраске

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

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

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

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

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

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

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

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

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

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

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

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

Хм. Забавно. Новость от 2018 года. https://nplus1.ru/news/2018/04/10/chromatic-number

Уже 4 красок мало?

mayton
Хм. Забавно. Новость от 2018 года. https://nplus1.ru/news/2018/04/10/chromatic-number Уже 4 красок мало?

В данной работе работает шестиугольник, к которому пристыкован шестиугольник.
Во всех вершинах (кроме крайних ?) сходятся 3 грани.
6+6=12.

Есть ещё один вариант.
8+4=12.

Восьмиугольник и четырехугольник.
Во всех вершинах сходятся 3 грани.

Здесь появляется интересная задачка:
найти ещё картинки (или графы), повторяющиеся из одних и тех же сторон (или группы сторон) между гранями, где в вершине картинки только 3 грани.

Например, ещё:

в сотах или в шестиугольниках, как в статье, вместо вершины будет треугольник.

Получаем 12-угольник и треугольник.

А далее, 24 и 3, 48 и 3 и т.д.

Ошибся:

12, 6 и 3
24, 12, 6 и 3
48, 24, 12, 6 и 3
и т.д.

Был в форумах такой Рэт-Крысопыт. Многим он запомнился хроническим депрессивным настроением
и жалобами на неудачи. Читатели ПТ вкурсе.

Но кроме этого он решал задачу изоморфизма графов на сях. И на тот момент лучше чем аналоги
и интернетах. Исходник он мне передавал но я к сожалению его прое.. не сохранил вобщем.