New answers tagged

1

Your reduction was polynomial in the number N. To show that Primes is in NP, you need a reduction that is polynomial in the size of N, not in the number N itself. For example, one trillion stored in binary only takes 40 bits. So you are not allowed "polynomial in one trillion" but only "polynomial in 40" to show that a number around one ...


3

As you have stated, $Composites\in NP$ and $\overline{Primes}=Composites$. Hence, what you proved is that $Primes\in co-NP$. There is no easy reduction $Primes\le_p Composites$, since you will have to do the following task: given a number $n$, return another number $n'$ such that $n$ is prime if and only if $n'$ is composite. What you did wasn't a reduction, ...


3

Here is the definition of NP: A language $L$ is in NP if there is a polytime machine $T$ and a polynomial $p$ such that: If $x \in L$ then there exists $y$ of size at most $p(|x|)$ such that $T(x,y) = 1$. If $x \notin L$ then for all $y$ of size at most $p(|x|)$, $T(x,y) = 0$. We think of $y$ as a witness. Composites is in NP since $y$ could be a ...


1

You can transform the Subset Sum instance by multiplying all the weights of the "packages" and the target weight by 51. Notice how, in the modified instance, adding any additional weight between 0 and 50 cannot change whether the target weight can be attained. If up to 10 packages with weight 5 were available, then you could only add weights up to ...


2

Yes: we know that being in $NP$ is equivalent to having a polynomial verifier. Let $M$ be the verifier of $B$ (getting an input $x$ and a witness $w$), and let $f$ be the reduction function. Then, define $M'(x,w):=M(f(x), w)$. Since $x\in A\iff f(x)\in B$, then $\exists w. M(f(x),w) \iff f(x)\in B\iff x\in A$, and thus $M'$ is a verifier for $A$, hence $A\in ...


0

(Note: the below proof may have some issues raised in the comments. I am in the processing of addressing the issues.) The following "end-character" method was suggested in the comment above, as well as private communication with some others. Any mistakes are my own. We construct a polynomial-time reduction from the Gold problem (arbitrary alphabet ...


1

Regarding 1: yes, since $B$ is $\mathsf{NP}$-complete it must be $\mathsf{NP}$-hard, i.e., for every problem $C$ in $\mathsf{NP}$ we have $C \le_P B$. Since $A \in \mathsf{P} \subseteq \mathsf{NP}$, we can pick $C=A$. This is true regardless of whether $\mathsf{P}=\mathsf{NP}$. Notice, however, that we are using the fact that $B$ is $\mathsf{NP}$-complete. ...


0

Take a look at the definition of NP-complete, it might help. How fast can we compute $MST^*$? Try to use this in conjunction with the assumption you made.


1

You just need to add $n$ (where $n$ is the order of the graph) vertices with no additional edges.


0

Double the graph size: make two clones of the input $G_1,G_2$ and now create the (not connected) graph $\hat G$ that will consist of the two clones $G_1,G_2$. Now a half-hamiltonian path in $\hat G$ is either going through all $G_1$ or all $G_2$ (but not both, since they are not connected) and thus would be a hamiltonian path in $G$.


Top 50 recent answers are included