Given $f : \{0,1\}^* \to \{0,1\}$ and $n \in \mathbb{N}$, we define $\textsf{Prob}(f,n)$ as the following problem:

Find an $x \in \{0,1\}^n$ such that $f(x) = 1$.

A machine solving $\textsf{Prob}(f,n)$ would have $f$ encoded as a bit-string representing another machine computing $f$ and would have $n$ encoded in binary.

$\textsf{Prob}(f,n)$ generalizes some problems. For example:

  • If $f$ is a Boolean logical proposition with $n$ variables, then $\textsf{Prob}(f,n)$ would be the search problem that corresponds to the SAT of $f$.

  • If $f$ is the decider for a language, then $\textsf{Prob}(f,n)$ would be the problem of finding an $n$-bit string in that language.

Has $\textsf{Prob}(f,n)$ been studied in the literature (presumably with another name)? Is there already a name for this problem? What would be a good starting point to find papers on this problem in the research literature?

What problems are similar to this problem?

Is there linear-time $f$ such that $\textsf{Prob}(f,n)$ has no better algorithm than brute force? Formally, is there $f$ such that evaluating $f(x)$ is in $\textsf{DTIME}(O(\lvert x \rvert))$ and $\textsf{Prob}(f,n) \in \textsf{DTIME}(\Omega(2^n))$?

  • 1
    $\begingroup$ Are there any restrictions on the complexity of $f$? If $f$ is uncomputable, then the problem is undecidable. If $f$ can be evaluated in polynomial time, then the problem is in $NP$, since we can guess which bit-string has the property and verify it. Any version of the problem is going to be $NP$-hard, since you can use the boolean-evaluation of a logic formula to simulate SAT with this problem. $\endgroup$ – jmite Mar 23 '15 at 16:56
  • $\begingroup$ I have been assuming that $f$ can be evaluated in polynomial time. I was trying to find out if there exists such $f$ that the above problem is in EXP but not in P. $\endgroup$ – edom Mar 23 '15 at 17:42
  • $\begingroup$ Since $P$ vs $NP$ is unknown, your best bet for that is going to be to put some $EXPTIME$-complete problem in this form. Maybe something where you let $f$ be the function determining whether a Turing Machine halts on its given input in $n$ or less steps? If you encode the input in binary, this is $EXPTIME$-complete. $\endgroup$ – jmite Mar 23 '15 at 17:51
  • $\begingroup$ @jmite If $f$ is polytime computable, the problem in the question is only in NP if $n$ is given in unary. $\endgroup$ – David Richerby Mar 23 '15 at 18:12
  • $\begingroup$ @DavidRicherby ah, that's true, I missed that. $\endgroup$ – jmite Mar 23 '15 at 18:49

The problem, as specified, takes at least exponential time to solve: merely outputting a string $x$ that satisfies $f(x)=1$ takes $\Theta(n)$ time (since $x$ is $n$ bits long), and this is exponential in the length of the input in the worst case (if $f$ has a short description, then the input length is $\Theta(\lg n)$ bits. This is a consequence of the fact that $n$ is specified in binary.

If $n$ is specified in unary and the running time of $f$ is guaranteed to be polynomial in $n$, the problem is NP-hard, and the corresponding decision problem is NP-complete. It is at least as hard as SAT, because any SAT formula can be encoded as a program $f$. Also, it is no harder than SAT, as any program whose running time is polynomial in $n$ can be expressed as a circuit of size polynomial in $n$; then the problem becomes equivalent to CircuitSAT, which is also NP-complete by a standard reduction (basically, the Tseitin transform).

So the unique aspects of this problem come from (a) the fact that $n$ is expressed in binary, and (b) the lack of any guarantee on the running time of $f$.

For your last question, you have to be a little bit careful. If you fix $f$ and specify $n$ in unary, the problem seems unlikely to require $\Omega(2^n)$ time. In particular, there is an infinite advice string $A$ such that the answer to the input $n$ is $A_n$. This shows that there is a non-uniform polynomial time algorithm for this problem, if you fix $f$ and express $n$ in unary (i.e., the problem is in P/poly); this would be surprising, as it implies NP is contained in NP/poly, which is not expected to occur. To avoid trivial situations like this, you might want to treat the description of $f$ as part of the input, rather than fixing $f$.

This suggests we ask whether there exists a class of functions $f$ such that the problem requires $\Omega(2^n)$ time, yet where every function $f$ in the class can be computed in $O(n)$ time. I suspect the answer to that is likely to be yes if the strong exponential time hypothesis is true; simply take as your class of functions the set of SAT formulas of size $O(n)$. Note that this doesn't follow immediately from the strong exponential time hypothesis, due to the extra restriction that the formulas have size $O(n)$, but I would venture a guess that this restriction does not help algorithms solve SAT more efficiently. That said, the strong exponential time hypothesis is a very strong assumption.

Also, if we could prove that the answer to this question is yes, then I suspect we'd obtain a proof that the strong exponential time hypothesis is true. In particular, since $f$ can be computed in $O(n)$ time, there is a circuit that computes it in $O(n)$ time, so it can be expressed as a SAT formulas with $O(n)$ variables (using the Tseitin transform). If we knew that there was no algorithm to solve the resulting class of SAT instances in $O(2^n)$ time, then we'd know there is no algorithm to solve all SAT instances in $O(2^n)$ time, which implies the strong exponential time hypothesis. I think.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.