347 reputation
213
bio website
location
age
visits member for 3 years, 11 months
seen Dec 19 at 20:52

Dec
19
awarded  Constituent
Dec
8
awarded  Caucus
Nov
17
awarded  Popular Question
Sep
8
awarded  Popular Question
Jul
2
awarded  Curious
Apr
8
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.
Apr
8
revised If $P=NP$, prove that $L' \in NP$
deleted 123 characters in body
Apr
8
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.
Apr
8
revised If $P=NP$, prove that $L' \in NP$
added 42 characters in body
Apr
8
comment If $P=NP$, prove that $L' \in NP$
Yes I believe so since it was stated that $L \in NP$.
Apr
8
asked If $P=NP$, prove that $L' \in NP$
Apr
7
accepted Prove language is in $NP$ without using a reduction
Apr
7
asked Prove language is in $NP$ without using a reduction
Apr
5
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!
Apr
5
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?
Apr
4
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.
Apr
4
accepted Prove 2-HamiltonianCycle $\in \textbf{NP}$
Apr
4
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.
Apr
4
asked Prove 2-HamiltonianCycle $\in \textbf{NP}$
Feb
27
comment Prove $L$ = $\{\langle M \rangle$ | $M$ is a TM over $\{0,1\}$ and $\langle M \rangle \langle M \rangle \notin \mathcal{L}(M)\}$ is undecidable.
Awesome thanks!