Maximizing a skew-supermodular function

Given a skew-supermodular function $$p:2^V\to \mathbb{Z}$$ with a function evaluation oracle, is it possible to find a set $$X\subseteq V$$ in polynomial time such that $$p(X)=\max\{p(Y): Y\subseteq V\}$$ ? The problem is open even if $$p$$ is a crossing negamodular function.

It was shown by Toshimasa Ishii and Kazuhisa Makino that the problem is hard even for negamodular functions. More precisely, they showed that any algorithm for the posimodular function minimization problem requires $$\Omega(2^{\frac{n}{7.54}})$$ oracle calls. Furthermore, if the range of the set function is $$\{0,1\dots,d\}$$ , then $$\Omega(2^{\frac{d}{15.08}})$$ oracle calls are necessary.

Remarks

There are several polynomial-time combinatorial algorithms for minimizing a submodular function (which is equivalent to maximizing a supermodular function); see for surveys.