0
$\begingroup$

Given:

$L_1 = \{0^k1^k|k \in \mathbb{N}\}$

$L_2= \{1\}$

$L_1 \leq_p L_2$

There must be a function

$$f:Σ^* \rightarrow Σ^*$$ such that $$w \in L_1 \iff f(w) ∈ L_2$$

Let's say a word in $L_1$ is mapped to $1$ in $L_2$. If it is not in $L_1$ it is mapped to $0$.

So each word in $L_1$ is mapped to $1$.

So the input for the Oracle of $L_2$ would always be $1$?

Is this a correct Karp reduction?

$\endgroup$
  • 1
    $\begingroup$ Note that $f$ must be computable in polytime -- don't forget this. Also, what if your $f$? What is $f(0101)$? Don't forget that $f$ must be defined on all words. $\endgroup$ – chi Jun 26 '18 at 13:39
  • $\begingroup$ as I said if it is not in L1 f(0101) then f results in 0 $\endgroup$ – simplesystems Jun 26 '18 at 14:59
  • $\begingroup$ I think you have answered your question "So the input for the Orakel of L2 would always be 1?", haven't you? I think the argument above is fine, as long as you justify why $f$ is polytime. $\endgroup$ – chi Jun 26 '18 at 16:11
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Jun 26 '18 at 16:18
  • $\begingroup$ It would be helpful to tell us why you suspect your answer is wrong. Also, the way to tell whether your answer is correct is to prove it. So, refer back to the definitions. Does your function $f$ meet all of the conditions in the definition of a Karp reduction? You should be able to check that for yourself. If not, specifically which condition are you unsure about, and why? I suggest editing the question to provide all of this information, if you still want an answer. $\endgroup$ – D.W. Jun 26 '18 at 16:19

Your Answer

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

Browse other questions tagged or ask your own question.