Заполнение аргумента

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

Пример

Доказательство того, что P = NP подразумевает EXP = NEXP, использует «заполнение».

$\mathrm {EXP} \subseteq \mathrm {NEXP}$ по определению, поэтому достаточно показать $\mathrm {NEXP} \subseteq \mathrm {EXP}$.

Пусть L — язык в NEXP. Поскольку L находится в NEXP, существует недетерминированная машина Тьюринга M , которая решает L за время. $2^{n^{c}}$ для некоторой постоянной c . Позволять

$L'=\{x1^{2^{|x|^{c}}}\mid x\in L\},$

где '1' — символ, не встречающийся в L . Сначала мы покажем, что $L'$ находится в NP, то мы воспользуемся детерминированной полиномиальной машиной времени, заданной формулой P = NP, чтобы показать, что L находится в EXP.

$L'$ может быть решено за недетерминированное полиномиальное время следующим образом. Учитывая ввод $x'$, убедитесь, что оно имеет вид $x'=x1^{2^{|x|^{c}}}$ и отклонить, если это не так. Если он имеет правильную форму, смоделируйте M ( x ). Моделирование принимает недетерминированный $2^{|x|^{c}}$ время, которое является полиномиальным по размеру входных данных, $x'$. Так, $L'$ находится в НП. По предположению P = NP существует также детерминированная машина DM , которая решает $L'$ за полиномиальное время. Затем мы можем решить L за детерминированное экспоненциальное время следующим образом. Учитывая ввод $x$, симулировать $DM(x1^{2^{|x|^{c}}})$. Это занимает только экспоненциальное время в зависимости от размера входных данных, $x$.

The $1^{d}$ называется «заполнением» языка L . Этот тип аргумента также иногда используется для классов пространственной сложности , альтернативных классов и ограниченных альтернативных классов.

См. также

• Наполняемый язык

Ссылки

• Арора, Санджив ; Барак, Боаз (2009), Вычислительная сложность: современный подход , Кембридж , с. 57, ISBN  978-0-521-42426-4