Questions tagged [padding]
The padding tag has no usage guidance.
2
questions
6
votes
1
answer
506
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 ...
- 3,796
25
votes
4
answers
3k
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 ...
- 1,548