Аргумент заполнения

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

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

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

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

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

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

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

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

• Язык с возможностью добавления

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