# black-box function optimization with binary vector input: terminology and NP-hardness proof

I have a black-box function optimization problem: $$\arg\max_{\vec{x}} \; f(\vec{x}, \vec{y}) \\\text{subject to } \vec{x} \in \mathbb{Z}_2^N, \|\vec{x}\|_1=K, K<N, \vec{y} \in \mathbb{Z}_2^M$$

The function $f(\cdot)$ is a black-box function whose output I can only simulate: I cannot access its exact form. The variables $\vec{x}$ and $\vec{y}$ are two binary vectors as the inputs of $f(\cdot)$. Given $\vec{y}$, I am seeking the optimal $\vec{x}$ that maximizes $f(\vec{x},\vec{y})$.

My questions:

1. Is there similar research having the same form as my problem? What is the terminology for such problems?
2. The brute force method to do the optimization is to exhaust all $\binom{N}{K}$ possible $\vec{x}$. Is this problem NP-hard? How can we prove this problem is an NP-hard problem?
3. In practice there should be some heuristics and techniques to be used to speed up the search and return an approximate optimal solution. Can someone point me out the names of possibly feasible techniques?
• Your problem cannot be NP-hard (or not NP-hard) since oracle problems are not decision problems. – Yuval Filmus Dec 26 '17 at 8:32

NP-hardness is a property of languages, that is, of subsets of $\Sigma^*$ for some finite alphabet $\Sigma$. Your problem is not of this form, since you also need to give the algorithm access to the function $f$. Such problems are known as "optimization with a value oracle" (and several other similar names) — the value oracle in your case is the function $f$.

To show that such a problem is hard, we typically given an information-theoretic lower bounds on the number of value oracle calls of any valid algorithm. This captures much, but not all, of the difficulty of solving the problem (it ignores the computational complexity of deciding which questions to ask the oracle). In your case, it is easy to show that any valid algorithm must query the oracle at all possible inputs, using an adversary argument. This makes your problem not so interesting.

In practice, problems tend to have more structure. For example, if you know that for each $\vec{y}$, the function $\vec{x} \mapsto f(\vec{x},\vec{y})$ is submodular, then you can use approximation algorithms for (non-monotone) submodular maximization. In some cases, for example maximizing supermodular functions, there are efficient algorithms that find an optimal solution. In other cases, for example maximizing submodular functions, finding even an $\alpha$-approximate maximum can be hard (requiring exponentially many value oracle queries) if $\alpha$ is too close to 1, but at some point the problem becomes easy again (can be solved in polynomial time).

Any heuristics to your problem will have to rely on some properties of your function. So your first task is to learn more about the structure of your function. In some cases, such as cryptography, there is nothing more to learn, and then there is no real way to speed up the search. But in most optimization contexts you are able to say more about your function, at least roughly, and this informs the algorithms and heuristics that you subsequently use.