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

Padding argument - Wikipedia

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

Пример

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

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

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

возможно решил за недетерминированное полиномиальное время следующим образом. Данный ввод , убедитесь, что он имеет вид и отклонить, если это не так. Если он имеет правильную форму, смоделируйте М (х). При моделировании используются недетерминированные время, которое является полиномом от размера входа, . Так, находится в НП. По предположению P = NP существует также детерминированная машина DM это решает за полиномиальное время. Затем мы можем решить L в детерминированном экспоненциальном времени следующим образом. Данный ввод , моделировать . Это занимает только экспоненциальное время в размере ввода, .

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

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

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