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?


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.