HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

So if a problem is more difficult the language it represents is smaller?

Submitted by: @import:stackexchange-cs··
0
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$?

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.

Context

StackExchange Computer Science Q#102213, answer score: 7

Revisions (0)

No revisions yet.