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.

  • 1
    $\begingroup$ Well, 2. obviously holds for polynomial-length output. ​ ​ $\endgroup$
    – user12859
    Jan 12, 2018 at 11:09
  • $\begingroup$ @RickyDemer Yes, that's why I suggested that assumption for 1 only. $\endgroup$
    – Discrete lizard
    Jan 12, 2018 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, 2018 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, 2018 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, 2018 at 11:28


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.