Question

For any solvable decision problem, there is a way to encode instances of a problem so that the corresponding language can be recognized by a TM with............... time complexity
a) linear
b) exponential
c) polynomial
d) none of these

Answer 1

Answer on Question #43232 – Math – Other

For any solvable decision problem, there is a way to encode instances of a problem so that the corresponding language can be recognized by a TM with... time complexity

a) linear

b) exponential

c) polynomial

d) none of these

Solution:

We define such an encoding, $e$, as follows

$$e(x) = \begin{cases} 1 \text{ x, if } x \text{ is a yes - instance of the decision problem} \\ 0 \text{ x, otherwise} \end{cases}$$

The decision problem is solvable, so $e$ is computable. $e(x)$ can be recognized in a single move by examining the first character of the input. Linear time complexity means there are non-negative constants $m, b$ such that $\tau_T(|x|) \leq mx + b$ where $\tau_T$ is the time complexity of the machine solving the decision problem. Clearly that is true for $m = 0$ and $b = 1$.

Answer:

a) linear.

www.AssignmentExpert.com