I am a beginner in the computer science track. I have some problems with the following problems

Problem 1: Assume that $NP \ne coNP$. If $L_1, L_2 \in NP$, is $\bar{L_1} \cap L_2$ necessarily in $coNP$.

My attempt: I intend to choose $L_1, L_2$ such that $L_1= \emptyset $, $L_2$ is in $NP$ complete. Then $\bar{L_1} \cap L_2 = L_2$. $L_2$ is in $NP$ complete. Becaues $NP \ne coNP$ then the complement of $L_2$ (denoted by $\overline{L_2}$) is not in $NP$. Then $L_2$ is not in $coNP$.

Could you please help me with checking my work?

Problem 2: What is wrong with the following proof of $P \neq N P$ ?

Suppose that $P=NP$. Then, there exists an algorithm $A$ and a polynomial $p(n)$ such that SAT is decided by $A$ in time $O(p(n))$. Assume that $p(n)=O\left(n^{37}\right)$. By the Time Hierarchy Theorem, there exists a problem $P \in \operatorname{DTIME}\left(n^{38}\right)$ such that $P \notin \operatorname{DTIME}\left(n^{37} \log n^{37}\right)=$ DTIME $\left(n^{37} \log n\right)$. Since SAT is NP-complete, we can reduce $P$ to SAT and decide it in time $O\left(n^{37}\right)$. But we have just shown that $P$ requires time $\omega\left(n^{37} \log n\right)$. This leads to a contradiction, hence the assumption $\mathrm{P}=$ NP must be false.

My attempts: I think the proof is wrong because based on Time Hierarchy Theorem, we have $$\operatorname{DTIME}(o(n^{37})) \subsetneq \operatorname{DTIME}(n^{37} \log n^{37} )$$

So I think that the statement: "there exists a problem $P \in \operatorname{DTIME}\left(n^{38}\right)$ such that $P \notin \operatorname{DTIME}\left(n^{37} \log n^{37}\right)=$ DTIME $\left(n^{37} \log n\right)$ " is a wrong statement.

Could you kindly verify my assessment of this proof and offer any further insights you may have on the matter? I genuinely appreciate your time and assistance in helping me navigate these challenging problems.

  • $\begingroup$ Please ask only one question per post. We generally discourage "please check whether my answer is correct", as the answer is unlikely to be useful to future visitors. $\endgroup$
    – D.W.
    Oct 28, 2023 at 4:09


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.