NP-полные задачи и их решатели (SAT solvers и т.п.)

[maxal]

MiniSAT - решатель задачи ВЫП (SAT), решатель задач псевдо-булева программирования и минимизатор КНФ (CNF) в одном флаконе. Распространяется под свободной лицензией MIT с открытыми исходными текстами.

QUALEX-MS, который находит максимальную взвешенную клику или независимое множество вершин в графе, а также другие программы Стаса Бусыгина. См. также модерируемую Стасом ньюс-группу algorithm-forge, посвященную обсуждению решений сложных задач.

Reactive Search, a History-Sensitive Heuristic for Max-Sat

Решатели Maximum Clique in Graphs (MAX-CLIQUE), Graph Partitioning (equicut), Quadratic Assignment Problem (QAP)