# If $NP \ne coNP$, $L_1, L_2 \in NP$, then is it necessary for $\bar{L_1} \cap L_2 \in NP$ and checking the proof of $P \ne NP$

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.

• 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.
– D.W.
Oct 28, 2023 at 4:09