3
$\begingroup$

This comment by @DerekElkins suggests a general method of constructing decision problems for problems with bit-strings as output, of which a slightly formalised version is the following:

Given a problem $X$, where we expect output for input $x$ to be $X(x)$, construct the following decision problem $B_X$: Given $(n,x)$ for some $n\in \mathbb{N}$, does the $n$-th bit of $X(x)$ exist and is it equal to $1$?

Clearly, this produces a decision problem for any problem $X$. However, the resulting 'bit-checking' problem may be easier than the original problem $X$. A simple case is when $X(x)$ is exponential in $x$: Suppose $X(m)$ is listing all permutations of $1,\ldots,m$ in lexicographical order. Then clearly $X$ can only be solved in $\Omega(m!)$, but detecting a single bit means we only have to check a single permutation, which can be found in polynomial time. So, in this case, the 'bit-checking' problem is easier than the original.

Therefore, I wondered if there is a general procedure that creates a decision problem that isn't 'easier', for any of the following definitions of 'isn't easier':

  1. $X$ can be solved in $\Theta(f(x))$ if and only if $B_X$ can be solved in $\Theta(f(x))$
  2. $X$ is in $P$ if and only if $B_X$ is in $P$

I'm ok with additional assumptions if those are convenient, such as assuming that the output $X(x)$ is polynomial in $x$ for case 1 or any other (general) subset of problems.

$\endgroup$
  • 1
    $\begingroup$ Well, 2. obviously holds for polynomial-length output. ​ ​ $\endgroup$ – user12859 Jan 12 '18 at 11:09
  • $\begingroup$ @RickyDemer Yes, that's why I suggested that assumption for 1 only. $\endgroup$ – Discrete lizard Jan 12 '18 at 11:13
  • 1
    $\begingroup$ Conversely, when $X$'s output length is not bounded above by a polynomial, $X$ can't be $\hspace{.83 in}$ solved by $P$, so 2. holding is equivalent to $B_X$ not being in $P$. ​ ​ $\endgroup$ – user12859 Jan 12 '18 at 11:25
  • $\begingroup$ Your use of $\Theta(f(x))$ for both sides of 1. might make the answer depend $\hspace{1.86 in}$ on your precise model of computation. ​ ​ $\endgroup$ – user12859 Jan 12 '18 at 11:25
  • $\begingroup$ As far as I'm concerned, you can pick any reasonable model of computation. If you want a precise one, the RAM model should probably be fine. $\endgroup$ – Discrete lizard Jan 12 '18 at 11:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.