I'm reading the definition of polynomial time reducible:

Let $L_1, L_2$ be two language. If $L_1$ is polynomial time reducible to $L_2$ then exists $f:\{0,1\}^*$ s.t. $\forall x\in\{0,1\}^*$ $$x\in L_1\iff f(x)\in L_2$$

For me this means the $L_1$ may be bigger (in cardinality) than $L_2$, but $L_2$ is more difficult since $L_1$ can be solved after reduced to $L_2$?

  • $\begingroup$ How would define the cardinality of an infinite set being larger than another infinite set (both being countable sets)? $\endgroup$ – dkaeae Dec 31 '18 at 14:53
  • $\begingroup$ You can find examples in which $L_1$ is a strict subset of $L_2$ (and vice versa). $\endgroup$ – Yuval Filmus Dec 31 '18 at 15:17

$L_1$ and $L_2$ are always countably infinite, and thus "equally big".

If any language is finite, then it is "constant time" recognizable.

  • $\begingroup$ I forgot this fact that they're both infinite... Thanks! $\endgroup$ – Kindred Dec 31 '18 at 17:31

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.