О генерической сложности проблемы кластеризации графов с ограничениями на размер кластеров

Изучается генерическая сложность проблемы кластеризации графов с ограничением $p$ на размеры кластеров при $p \geq 3$. В этой задаче структура взаимосвязей объектов задаётся с помощью графа, вершины которого соответствуют объектам, а рёбра соединяют похожие объекты. Требуется разбить множество объектов на попарно непересекающиеся группы (кластеры) ограниченного числом $p$ размера так, чтобы минимизировать число связей между кластерами и число недостающих связей внутри кластеров. Доказывается, что при условии $\text{P} \neq \text{NP}$ и $\text{P}=\text{BPP}$ для этой проблемы не существует полиномиального сильно генерического алгоритма. Сильно генерический алгоритм решает проблему не на всём множестве входов, а на подмножестве, последовательность частот которого при увеличении размера экспоненциально быстро сходится к $1$.