О генерической сложности проблем $3$-раскраски графов

Изучается генерическая сложность двух вариантов проблемы о $3$-раскраске графов: проблема распознавания и проблема поиска $3$-раскраски графа. Для обеих проблем эффективных полиномиальных алгоритмов неизвестно. Проблема поиска $3$-раскраски используется в известном криптографическом протоколе Блюма для доказательства с нулевым разглашением. Предлагается полиномиальный генерический алгоритм для проблемы распознавания $3$-раскраски графа. Для проблемы поиска $3$-раскраски доказывается, что если $\text{P} \neq \text{NP}$ и $\text{P}=\text{BPP}$, то существует подпроблема этой проблемы, для которой нет полиномиального генерического алгоритма. Полученный результат является теоретическим обоснованием применения проблемы поиска 3-раскраски графа в криптографии, где нужно, чтобы проблема взлома криптоалгоритма была трудной для почти всех входов.