Об аппроксимационной сложности задачи о минимальном комитете

Изучается комбинаторная задача о минимальном комитете. Известно, что эта задача является ΝΡ-трудной. В статье показано, что если справедливо условие ΝΡ∉ΤΙΜΕ(mO(log log m)), то для произвольного ε > 0 не существует приближенного алгоритма задачи M F S с точностью (1 — ε) ln m.