“Padding argument”的意思、由来-开放百科全书

词条

Padding argument

释义

Example
References

In computational complexity theory, the padding argument is a tool to conditionally prove that if some complexity classes are equal, then some other bigger classes are also equal.

Example

The proof that P = NP implies EXP = NEXP uses "padding". by definition, so it suffices to show .

Let L be a language in NEXP. Since L is in NEXP, there is a non-deterministic Turing machine M that decides L in time for some constant c. Let

where 1 is a symbol not occurring in L. First we show that is in NP, then we will use the deterministic polynomial time machine given by P = NP to show that L is in EXP.

can be decided in non-deterministic polynomial time as follows. Given input , verify that it has the form and reject if it does not. If it has the correct form, simulate M(x). The simulation takes non-deterministic time, which is polynomial in the size of the input, . So, is in NP. By the assumption P = NP, there is also a deterministic machine DM that decides in polynomial time. We can then decide L in deterministic exponential time as follows. Given input , simulate . This takes only exponential time in the size of the input, .

The is called the "padding" of the language L. This type of argument is also sometimes used for space complexity classes, alternating classes, and bounded alternating classes.

References

{{Citation

| last1=Arora | first1=Sanjeev | authorlink1=Sanjeev Arora
| last2=Barak | first2=Boaz
| title=Computational Complexity: A Modern Approach
| url = http://www.cs.princeton.edu/theory/complexity/
| publisher=Cambridge
| year=2009
| isbn=978-0-521-42426-4
| page = 57
}}{{comp-sci-theory-stub}}{{DEFAULTSORT:Computational Complexity Theory}}

1 : Computational complexity theory

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。