Questions tagged [padding]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
6
votes
1answer
424 views

Lower bounds and class separation

Consider the language $A=\{0^{k}1^{k}|k\geq0\}$ . On Sipser's book "Introduction to the Theory of Computation" an algorithm with running time $O(n\log n)$ is given, on single-tape TM. We also know ...
25
votes
4answers
2k views

Why do equalities between complexity classes translate upwards and not downwards?

Hey Guys, I understand that the padding trick allows us to translate complexity classes upwards - for example $P=NP \rightarrow EXP=NEXP$. Padding works by "inflating" the input, running the ...