# 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$.
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).