342 reputation
111
bio website
location
age
visits member for 3 years, 8 months
seen Sep 10 at 23:11

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!
Feb
27
accepted 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.
Feb
26
asked 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.
Feb
14
asked Prove that $\overline{L}$ is not recognizable by showing that $B_{TM} \le_m L$