# Tag Info

Let $L\in NP$. Thus, $L\le_p A$. Since $A\in coNP$, then $L\in coNP$. Hence, $NP\subseteq coNP$. Now, let $L\in coNP$. Thus, $\overline{L} \in NP$ and therefore $\overline{L}\le_p A$. From reduction properties, we know that $L\le_p \overline{A}$ holds as well. Now, since $A\in coNP$ then $\overline{A}\in NP$. Hence, $L\in NP$, and therefore we get that $coNP\... 1 Even with your restriction$D$is undecidable. You can still reduce the halting problem of a TM$A$on a word$x$to$D$. Construct a TM$B$that simulates$A$on$x$. If$A$halts,$B$accepts its input. Otherwise$B$runs forever. Clearly then$A$halts on$x$iff$B \not\in D$. Note that you can always construct$B$such that$B \neq M_D$by performing ... 3 Please feed this program (pseudo-code) into yours. for every integer n > 3: has_solution := false for every prime p < 2*n: if (2*n - p) is a prime: has_solution := true break from inner loop if not has_solution: halt Congratulations! You have solved the Goldbach's conjecture! A step-by-step analysis of your program when it is ... 2 The halting problem asks whether a particular Turing Machine will halt if given a particular input. If you don't consider the input, you can't claim to solve the halting problem; a given program might halt for some inputs and not for others. You can substitute the input with a static initialisation without altering the sense of this objection. It's not ... 2 Your problem is equivalent to the following: Given an integer$k$, does there exist a bisection of value$k$? In particular, every bisection is a cut, so if there exists a bisection of value$k$, then there also exists a cut of value$k$; if there does not exist a bisection of value$k$, then there does not exist both a cut and a bisection of value$k\$. This ...