New answers tagged

2

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 ...


Top 50 recent answers are included