patternMinor
So if a problem is more difficult the language it represents is smaller?
Viewed 0 times
problemthemorelanguagesmallerrepresentsdifficult
Problem
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$?
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$?
Solution
$L_1$ and $L_2$ are always countably infinite, and thus "equally big".
If any language is finite, then it is "constant time" recognizable.
If any language is finite, then it is "constant time" recognizable.
Context
StackExchange Computer Science Q#102213, answer score: 7
Revisions (0)
No revisions yet.