# Are there name and literature for this SAT-like problem?

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))$?

• 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. – jmite Mar 23 '15 at 16:56
• 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. – edom Mar 23 '15 at 17:42
• 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. – jmite Mar 23 '15 at 17:51
• @jmite If $f$ is polytime computable, the problem in the question is only in NP if $n$ is given in unary. – David Richerby Mar 23 '15 at 18:12
• @DavidRicherby ah, that's true, I missed that. – 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.