Самой первой NP –полной задачей стала задача нахождения клик графа, то есть полных подграфов данного графа с конкретным числом вершин…

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

Мало радости признаваться в собственной бестолковости и некомпетентности, но проблема трудно решаемых задач для меня существует в несколько извращенном виде.