computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...

, the padding argument is a tool to conditionally prove that if some

complexity classes In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms of a ...

are equal, then some other bigger classes are also equal.

Example

The proof that P = NP implies

EXP Exp may stand for: * Exponential function The exponential function is a mathematical function denoted by f(x)=\exp(x) or e^x (where the argument is written as an exponent). Unless otherwise specified, the term generally refers to the pos ...

NEXP In computational complexity theory, the complexity class NEXPTIME (sometimes called NEXP) is the set of decision problems that can be solved by a non-deterministic Turing machine using time 2^. In terms of NTIME, :\mathsf = \bigcup_ \mathsf(2^) ...

uses "padding".

\mathrm \subseteq \mathrm

by definition, so it suffices to show

\mathrm \subseteq \mathrm

. Let ''L'' be a language in NEXP. Since ''L'' is in NEXP, there is a

non-deterministic Turing machine In theoretical computer science, a nondeterministic Turing machine (NTM) is a theoretical model of computation whose governing rules specify more than one possible action when in some given situations. That is, an NTM's next state is ''not'' comp ...

''M'' that decides ''L'' in time

2^

for some constant ''c''. Let :

L'=\,

where '1' is a symbol not occurring in ''L''. First we show that

L'

is in NP, then we will use the deterministic polynomial time machine given by P = NP to show that ''L'' is in EXP.

L'

can be decided in non-deterministic polynomial time as follows. Given input

x'

, verify that it has the form

x' = x1^

and reject if it does not. If it has the correct form, simulate ''M''(''x''). The simulation takes non-deterministic

2^

time, which is polynomial in the size of the input,

x'

. So,

L'

is in NP. By the assumption P = NP, there is also a deterministic machine ''DM'' that decides

L'

in polynomial time. We can then decide ''L'' in deterministic exponential time as follows. Given input

x

, simulate

DM(x1^)

. This takes only exponential time in the size of the input,

x

. The

1^d

is called the "padding" of the language ''L''. This type of argument is also sometimes used for

space complexity The space complexity of an algorithm or a computer program is the amount of memory space required to solve an instance of the computational problem as a function of characteristics of the input. It is the memory required by an algorithm until it ex ...

classes, alternating classes, and bounded alternating classes.

References

* {{DEFAULTSORT:Computational Complexity Theory *