2
$\begingroup$

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

$\endgroup$
0

2 Answers 2

3
$\begingroup$

Hint: What is the definition of "NP-complete"?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.