Теорема .

Доказательство.
Зафиксируем во множестве языков

язык

. Рассмотрим последовательность многоугольников
![$\gamma_k=[L_0,L_{1k},\dots,L_{n_kk}]$ $\gamma_k=[L_0,L_{1k},\dots,L_{n_kk}]$](https://dxdy-04.korotkov.co.uk/f/3/a/0/3a0bf2534163daea449603a4b24e9f5282.png)
в пространстве

таких ,что

. Тогда верно следующее утверждение.
Лемма 1. Множество

можно представить в следующем виде:

Доказательство.
Опишем процедуру построения данного пространства : возьмём подстановку

такую ,что она будет переводить

-тую вершину

-угольника в

-ую вершину того же многоугольника. Ясно ,что вместе с обратной данной подстановке

они образуют группу с двумя элементами

. Пусть

,далее объединим их во множество

,учитывая ,что каждая из подстановок действует из

в

видим ,что каждая из них полиномиально вычислима . Таким образом , имеет место представление :

Учитывая то ,что само

имеет подмножествами только многоугольники рассматриваемой последовательности (это легко видеть) ,получаем требуемое.
Введем отображение

Пусть

и

,где

-

-ое простое число. Тогда очевидно ,что

- биекция. Теперь построим тем же ,что и в лемме 1 ,образом множество

-полных задач (далее NPC) :
Фиксируем

Далее строим многоугольники, как перед леммой 1 , устанавливая на множестве их вершин подстановки . Пусть группы рассматриваемых подстановок многоугольников ,при объединении ,также образуют множество

. Применяя лемму 1 для множества

,также видим ,что каждая подстановка полиномиально вычислима . Устанавливая отображение

,также легко установить ,что оно биективно . Таким образом

,что равносильно равенству

,что и требовалось доказать.
Оцените пожалуйста ,укажите на ошибки . Я считаю ошибкой в своем доказательстве то ,что не имея алгоритма перебора языков определенного класса сложности их просто нельзя перечислить. Это верно?