математика - Постройте схему полиномиального размера

Раскрашиваемость графа в два цвета равносильная отсутствию в нём циклов нечётной длины; эти циклы можно считать простыми.

Если $%A$% -- матрица смежности графа (фактически, это и есть заданная в условии функция $%f$%), то степени этой матрицы несут информацию о количестве путей заданной длины из каждой вершины в каждую (это известный теоретический факт). Рассматривая степени матрицы $%A$% с нечётными показателями, то есть $%A$%, $%A^3$%, $%A^5$%, ... (показатели можно брать не больше $%n$% ввиду анализа только простых циклов), мы должны прийти к тому, что все диагональные элементы этих матриц обязаны быть нулевыми.

Количество рассматриваемых матриц равно $%O(n)$%. Перемножение матриц, производимое по обычным формулам из линейной алгебры, требует полиномиального числа операций. Составляя схемы для всех упомянутых выше матриц и вычленяя из них информацию о диагональных элементах, мы получаем $%O(n^2)$% булевых переменных, для которых далее рассматривается схема-дизъюнкция. К ней надо добавить отрицание, чтобы получилась 1 на выходе в случае 2-раскрашиваемости графа. Общий размер такой схемы, очевидно, будет полиномиальным.