Р vs NP

[makxsiq]

Определение задачи $XZ$

Рассмотрим задачу $XZ$ следующего вида.
Число $Z$ из $n$ разрядов в виде последовательность из $n$ нулей и единиц хранится в памяти автомата $R$.
На входе автомату $R$ можно подавать любое двоичное число $x$ разрядности $n$, т.е. любую последовательность из $n$ нулей и единиц. Работа автомата $R$ заключается в побитном сравнении числа $x$ с числом $Z$.
Автомат $R$ отвечает на вопрос, равны или нет числа $x$ и $Z$. На выходе автомат $R$ выдает

$$\begin{cases}\ R(x)=1, x=Z\\R(x)=0, x \neq Z\end{cases}$$

Задача $XZ$ заключается в том, чтобы найти число $Z$ по известной длине $n$ двоичной записи $Z$.
Можно обращаться к автомату $R$ неограниченное количество раз с разными входными данными $x$ длины $n$.

Решение задачи $XZ$
Автомат $R$ можно представить в виде программы машины Тьюринга $MT R$.
Тогда задачу $XZ$ можно решить двумя способами:
1) полный перебор $2^n$ вариантов входных данных $x$ с таким же количеством (в худшем случае) запусков машины Тьюринга $MT R$,
2) анализ программы машины Тьюринга $MT R$ для извлечения из самой программы зашитого в программу числа $Z$.

Тезис 1
Сложность решения задачи $XZ$ способом 1 является экспоненциальной по $n$.
Доказательство.
В худшем случае для определения $Z$ может потребоваться перебрать $2^n$ возможных вариантов входных данных $x$.

Тезис 2
Сложность решения задачи $XZ$ способом 2 не является экспоненциальной по $n$.
Доказательство.
Сложность будет зависеть от размера и качества программы $MT R$, которые зависят от $n$ не экспоненциально.

Тезис 3
Любая задача класса $NP$ может быть представлена в виде задачи $XZ$.
Доказательство.
Рассмотрим NP-полную задачу "куб-змейка".
https://doi.org/10.2197/ipsjjip.21.368
http://strana-igr.ru/index.php?productID=488
Змейка состоит из 64 или, в облегченном варианте, 27 атомарных кубиков. Каждый атомарный кубик имеет либо прямое, либо угловое сквозное отверстие, через которое протянута нить, плотно соединяющая все атомарные кубики в змейку.
Головоломка заключается в том, чтобы собрать змейку в куб 4х4х4 или, в облегченном варианте, в куб 3х3х3, имея возможность вращать части змейки по сочленениям атомарных кубиков.
Последовательность поворотов атомарных кубиков для правильной сборки головоломки может быть закодирована в виде бинарного числа $Z$,
которое помещается в автомат $R$.
Любая попытка сборки головоломки в виде определенной последовательности поворотов атомарных кубиков может быть закодирована числом $x$.
Решение соответствующей задачи $XZ$ будет решением головоломки "куб-змейка".

[Pphantom]

Тема перемещена из форума «Дискуссионные темы (М)» в форум «Карантин»
по следующим причинам:

- отсутствуют доказательства тезисов.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.