Аргумент заполнения - Padding argument - Wikipedia

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

Пример

Доказательство того, что п  = НП подразумевает EXP  = NEXP использует «отступ». ${\displaystyle \mathrm {EXP} \subseteq \mathrm {NEXP} }$ по определению, поэтому достаточно показать ${\displaystyle \mathrm {NEXP} \subseteq \mathrm {EXP} }$.

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

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

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

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

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

Рекомендации

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