1
$\begingroup$

I'm struggling with the following question:

Define $Avg-P$ the class of all languages $L$ for which there exists a polynomial time Turing Machine $M$ such that for every $n$, for all but $\frac{2^n}{n}$ of the $2^n$ strings of length $n$, $M$ gives the correct answer to whether $x\in L$ or not. Prove that there exists $L\in DTIME(n^{\log n})$ which is not in $Avg-P$.

My attempt: I thought about using diagonalization. First we enumerate all Turing Machinges $M_1,M_2,M_3,...$. Now we define the following TM: for input $x$ of length $n$, simulate $M_n$ on input $x$ for $n^{\log n-1}$ steps. If the simulation halted, answer the opposite. Otherwise, reject. Now lets define $L(T)=L$. It's easy to see that $L\in DTIME(n^{\log n})$. Now let's assume towards contradiction that $L\in Avg-P$. Then there exists $M_i$ that gives the correct answer to whether $x\in L$ for all but $\frac{2^i}{i}$ of the $2^i$ strings of length $i$. But because $T$ simulates $M_i$ and answers the opposite, this is a contradiction.

The problem: I didn't find a way to make sure the simulation indeed halts for $M_i$, and answers the opposite as wanted. Any ideas how I can fix this solution/solve in another way?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.