WikiDer > Аргумент заполнения - Википедия

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

Пример

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

Позволять L быть языком в NEXP. С L находится в NEXP, есть недетерминированная машина Тьюринга M это решает L во время ${ Displaystyle 2 ^ {п ^ {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 ^ {| х | ^ {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