black-box function optimization with binary vector input: terminology and NP-hardness proof
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) &mdash; 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.