Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
given 2 lagnauges A,B which are npc. is there a reduction function from A to B $A \leq_PB$ ?
my idea was to say that since they are decideable, we can do this: $$ f(x) = \begin{cases} y \in B & \text{ } if x \in A \\y \notin B & \text{if }x \notin A.\end{cases} $$
is this is correct? or its not something that can be true? / depands on p equal or not equal to np
Hint: What is the definition of "NP-complete"?
Rather than spoon-feeding you the answer, I will tell you how to find the answer for yourself.
I suggest you write out the definition for the notation $\le_P$. Then, check whether your reduction meets the criteria for that notation.
Hint: the $P$ is important.
