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

NP-полнота проблемы разбиения графа на треугольники доказана Шейфером в 1974 г. и содержится в классической монографии М. Гэри и Д. Джонсона. В данной работе изучается генерическая сложность этой проблемы. Доказывается, что при условии $\text{P} \neq \text{NP}$ и $\text{P}=\text{BPP}$ для её решения не существует полиномиального сильно генерического алгоритма.