Об алгоритмической сложности описаний

В математике зачастую возникает следующая задача: необходимо дать наиболее простое описание для некоторого класса математических структур. В данной заметке мы кратко опишем один из подходов к решению этой задачи, основанный на оценке алгоритмической сложности индексных множеств.

Отметим одну из особенностей данного подхода: основным объектом его применения являются вычислимые структуры, т.е. такие структуры, отношения и операции в которых можно эффективно вычислять с помощью абстрактного вычислительного устройства. (Такими устройствами являются машина Тьюринга и обычный компьютер, которому разрешается обладать потенциально бесконечной памятью.) В качестве всем известного примера вычислимой структуры можно привести множество натуральных чисел с обычным порядком и стандартными операциями сложения и умножения. Для иллюстрации рассматриваемого подхода исследуем следующую проблему: насколько сложным может быть описание класса связных графов?

Напомним, что ориентированный граф задаётся множеством вершин и множеством дуг между этими вершинами. Грубо говоря, ориентированный граф можно представлять себе как семейство точек (вершин) на плоскости, между некоторыми из которых проведены стрелки (дуги). Граф является связным, если из любой его вершины можно добраться в любую другую, следуя по дугам графа. Все рассматриваемые графы будут не более чем счетными (то есть либо конечными, либо такими, для которых множество вершин можно занумеровать с помощью натуральных чисел).

Сопоставим эффективным образом каждому натуральному числу вычислимый ориентированный граф так, что каждому вычислимому графу будет соответствовать хотя бы одно число (или, говоря точнее, зафиксируем универсальную вычислимую нумерацию семейства всех вычислимых графов). Тогда алгоритмической сложности некоторого класса графов K будет соответствовать сложность множества номеров всех графов из K (это множество называют индексным множеством класса K). Поэтому вместо того, чтобы исследовать сам класс связных графов, мы можем ограничиться изучением его индексного множества.

Нужная нам оценка сложности получается следующим образом:

1) Граф G является связным, если:

для любой пары вершин x и y из G существует путь в G, ведущий из x в y.

Переписав это высказывание в виде формулы, можно понять следующее: существенную роль в нём играют только кванторы: квантор общности («для любой») и квантор существования («существует»). Отсюда получаем, что наше индексное множество лежит в классе  арифметической иерархии.

2) Проводя чуть более сложные рассуждения, нетрудно убедиться в том, что полученную оценку сложности нельзя уменьшить (например, до классов  или  арифметической иерархии).

В заключение отметим, что бывают и гораздо более сложные свойства: например, индексное множество для класса жёстких графов (то есть графов, не имеющих нетривиальных симметрий) является m-полным в классе  аналитической иерархии (в частности, отсюда следует, что для жёстких графов нельзя дать описание при помощи формулы исчисления предикатов).

Текст: Николай Баженов, кандидат физико-математических наук, ассистент, преподаватель ММФ НГУ, сотрудник Института математики им. С.Л. Соболева СО РАН

Фото: Анастасии Давлетгильдеевой, пресс-служба НГУ