В теории сложности вычислений , то набивка аргумент является инструментом для условно доказать , что если некоторые классы сложностей равны, то некоторые другие крупные классы также равны.
Пример
Доказательство того, что P = NP подразумевает EXP = NEXP, использует «заполнение». по определению, поэтому достаточно показать .
Пусть L - язык в NEXP. Поскольку L находится в NEXP, существует недетерминированная машина Тьюринга M, которая решает L за времядля некоторой постоянной c . Позволять
где 1 является символом , не входящие в L . Сначала покажем, чтонаходится в NP, то мы будем использовать детерминированную полиномиальную машину времени, заданную P = NP, чтобы показать, что L находится в EXP.
можно решить за недетерминированное полиномиальное время следующим образом. Данный ввод, убедитесь, что он имеет вид и отклоните, если это не так. Если он имеет правильную форму, смоделируйте M (x) . При моделировании используются недетерминированные время, которое полиномиально от размера входа, . Так,находится в НП. По предположению P = NP существует также детерминированная машина DM, которая решаетза полиномиальное время. Затем мы можем определить L за детерминированное экспоненциальное время следующим образом. Данный ввод, моделировать . Это занимает только экспоненциальное время в размере ввода,.
В называется «набивка» из языка L . Этот тип аргумента также иногда используется для классов пространственной сложности, чередующихся классов и ограниченных чередующихся классов.
Рекомендации
- Арора, Санджив ; Барак, Боаз (2009), Вычислительная сложность: современный подход , Кембридж , стр. 57, ISBN 978-0-521-42426-4