1337holiday
Reputation
352
Next privilege 500 Rep.
Access review queues
 Feb14 awarded Notable Question Dec19 awarded Constituent Dec8 awarded Caucus Nov17 awarded Popular Question Sep8 awarded Popular Question Jul2 awarded Curious Apr8 comment If $P=NP$, prove that $L' \in NP$ Yes thats exactly what i was thinking, the definition we use is that if the language can be verified in polynomial time then its in NP. Since $L'$ has a verifier $V$ then its in $NP$. I guess thats the answer, just thought I was missing something. Apr8 revised If $P=NP$, prove that $L' \in NP$ deleted 123 characters in body Apr8 comment If $P=NP$, prove that $L' \in NP$ @ShreevatsaR I've edited it a bit to include more of the original question but yes this is why I am confused myself, I don't know what exactly this question is asking. Apr8 revised If $P=NP$, prove that $L' \in NP$ added 42 characters in body Apr8 comment If $P=NP$, prove that $L' \in NP$ Yes I believe so since it was stated that $L \in NP$. Apr8 asked If $P=NP$, prove that $L' \in NP$ Apr7 accepted Prove language is in $NP$ without using a reduction Apr7 asked Prove language is in $NP$ without using a reduction Apr5 comment Prove 2-HamiltonianCycle $\in \textbf{NP}$ Perfect, makes sense now, my mistake was assuming that we were already given an $HC$ problem with a circuit, didn't take into account that there may not necessarily be a circuit, thanks! Apr5 comment Prove 2-HamiltonianCycle $\in \textbf{NP}$ Right, but I don't get your example that you provided because if we are transforming an $HC$ problem into a $2HC$ as you stated, how can your example have 4,5? If a problem is already $HC$ then shouldn't 4,5 be part of the cycle which is what makes it a Hamiltonian cycle? Apr4 comment Prove 2-HamiltonianCycle $\in \textbf{NP}$ ACtually I'm still a slight bit confused at the moment. Are we transforming $HC$ into $2HC$ or $2HC$ into $HC$ because all the examples I am seeing for the reductions are doing it the latter way. Apr4 accepted Prove 2-HamiltonianCycle $\in \textbf{NP}$ Apr4 comment Prove 2-HamiltonianCycle $\in \textbf{NP}$ Thanks for the tips however I have one concern for part b. According to the definition of $HC$, the cycle must include all vertices but in your example 4,5 are not in the cycle 1,3,2. So if all vertices are in the cycle, adding 1 vertex connecting to 2 different vertices already in the cycle will infact create a new cycle. Please correct me if im wrong. Apr4 asked Prove 2-HamiltonianCycle $\in \textbf{NP}$