Skip to main content
Tweeted twitter.com/#!/StackCompSci/status/530233511454593024
edited tags
Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393

If $L_1 \subseteq L_2$, is Is the identity function a many-one reduction from $L_1$a language to $L_2$super-set?

Rollback to Revision 2
Source Link
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

Got it If $L_1 \subseteq L_2$, appreciateis the help guys. Took meidentity a bit hahamany-one reduction from $L_1$ to $L_2$?

Got it! Thanks guys forI need help with a question.

Prove or disprove the following claim:

Let $f\colon \Sigma^* \to \Sigma^*$ be the identity function, i.e., $f(w) = w$ for all $w \in \Sigma^*$. Let $L_1$ and $L_2$ be two languages such that $L_1 \subseteq L_2$. Then $f$ is a many-to-one reduction from $L_1$ to $L_2$. In particular, if $L_2$ is decidable, $L_1$ is decidable as well.

I'm almost certain it's false, but I'm having a hard time with the justification. Can anyone help me out?

Got it, appreciate the help guys. Took me a bit haha

Got it! Thanks guys for the help

If $L_1 \subseteq L_2$, is the identity a many-one reduction from $L_1$ to $L_2$?

I need help with a question.

Prove or disprove the following claim:

Let $f\colon \Sigma^* \to \Sigma^*$ be the identity function, i.e., $f(w) = w$ for all $w \in \Sigma^*$. Let $L_1$ and $L_2$ be two languages such that $L_1 \subseteq L_2$. Then $f$ is a many-to-one reduction from $L_1$ to $L_2$. In particular, if $L_2$ is decidable, $L_1$ is decidable as well.

I'm almost certain it's false, but I'm having a hard time with the justification. Can anyone help me out?

deleted 448 characters in body; edited title
Source Link

If $L_1 \subseteq L_2$ Got it, isappreciate the identityhelp guys. Took me a many-one reduction from $L_1$ to $L_2$?bit haha

I need help with a question.

Prove or disprove the following claim:

Let $f\colon \Sigma^* \to \Sigma^*$ be the identity function, i.e., $f(w) = w$ for all $w \in \Sigma^*$. Let $L_1$ and $L_2$ be two languages such that $L_1 \subseteq L_2$. Then $f$ is a many-to-one reduction from $L_1$ to $L_2$. In particular, if $L_2$ is decidable, $L_1$ is decidable as well.

I'm almost certain it's false, but I'm having a hard time withGot it! Thanks guys for the justification. Can anyone help me out?

If $L_1 \subseteq L_2$, is the identity a many-one reduction from $L_1$ to $L_2$?

I need help with a question.

Prove or disprove the following claim:

Let $f\colon \Sigma^* \to \Sigma^*$ be the identity function, i.e., $f(w) = w$ for all $w \in \Sigma^*$. Let $L_1$ and $L_2$ be two languages such that $L_1 \subseteq L_2$. Then $f$ is a many-to-one reduction from $L_1$ to $L_2$. In particular, if $L_2$ is decidable, $L_1$ is decidable as well.

I'm almost certain it's false, but I'm having a hard time with the justification. Can anyone help me out?

Got it, appreciate the help guys. Took me a bit haha

Got it! Thanks guys for the help

added 113 characters in body; edited tags; edited title
Source Link
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512
Loading
Source Link
Loading