3
$\begingroup$

I am student learning Computational Complexity this semester. The text book is Sanjeev Arora et al. Computational Complexity, Cambridge University Press. I cannot solve the first problem in Chapter Three(p.77), which may be probably disappointing. The problem is as follow:

Show that the follow language is undecidable:
{M|M is a machine that runs in $100n^2+200$ time}.

3 Answers 3