Argument polstrování - Padding argument - Wikipedia

v teorie výpočetní složitosti, argument výplně je nástroj, který podmíněně dokáže, že pokud existuje třídy složitosti jsou si rovni, pak jsou si rovni i některé další větší třídy.

Příklad

Důkaz toho P  = NP naznačuje EXP  = NEXP používá „výplň“. ${ displaystyle mathrm {EXP} subseteq mathrm {NEXP}}$ podle definice, takže to stačí ukázat ${ displaystyle mathrm {NEXP} subseteq mathrm {EXP}}$.

Nechat L být jazykem v NEXP. Od té doby L je v NEXP, existuje nedeterministický Turingův stroj M to rozhoduje L včas ${ displaystyle 2 ^ {n ^ {c}}}$ pro nějakou konstantu C. Nechat

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

kde 1 je symbol, který se nevyskytuje v L. Nejprve to ukážeme ${ displaystyle L '}$ je v NP, pak k tomu použijeme deterministický polynomiální stroj času daný P = NP L je v EXP.

${ displaystyle L '}$ může být rozhodl v nedeterministickém polynomiálním čase následovně. Daný vstup ${ displaystyle x '}$, ověřte, zda má formulář ${ displaystyle x '= x1 ^ {2 ^ {| x | ^ {c}}}}$ a odmítnout, pokud se tak nestane. Pokud má správnou formu, simulujte M (x). Simulace je nedeterministická ${ displaystyle 2 ^ {| x | ^ {c}}}$ čas, který je polynomem velikosti vstupu, ${ displaystyle x '}$. Tak, ${ displaystyle L '}$ je v NP. Za předpokladu P = NP existuje také deterministický stroj DM to rozhoduje ${ displaystyle L '}$ v polynomiálním čase. Pak se můžeme rozhodnout L v deterministickém exponenciálním čase následovně. Daný vstup ${ displaystyle x}$, simulovat ${ displaystyle DM (x1 ^ {2 ^ {| x | ^ {c}}})}$. To trvá pouze exponenciální čas ve velikosti vstupu, ${ displaystyle x}$.

The ${ displaystyle 1 ^ {d}}$ se nazývá „výplň“ jazyka L. Tento typ argumentu se také někdy používá pro třídy složitosti prostoru, střídavé třídy a ohraničené střídavé třídy.

Reference

• Arora, Sanjeev; Barak, Boaz (2009), Výpočetní složitost: moderní přístup, Cambridge, str. 57, ISBN  978-0-521-42426-4