Comments on "Which combinatorial problem is similar to this problem?" Regarding the post Which combinatorial problem is similar to this problem?, it is quite hard to believe that, in the absence of information on the cost function, there is no algorithm better than exhaustive search to tackle this apparently easy-to-understand problem. I surfed the Internet and found something called the Weighted Constraint Satisfaction Problem, and I wonder whether this can be of any use in this case.
Any advise would be much appreciated.
EDIT: The problem I have at hand is a regression problem where each of $p$ inputs, $x_1, x_2, x_3, \cdots, x_p$, needs to undergo a variable transformation using one of $q$ functions from a set of available functions $F = \{ f_1, f_2, f_3, \cdots, f_q \}$. The cost function is the Mean Square Error (MSE) defined as $MSE = \frac{1}{n} \sum_{k=1}^n (y_k - \hat{y}_k)^2$, where $n$ is the number of samples and for each $k$, $y_k$ is an experimental value and $\hat{y}_k$ is the predicted value computed by some method (e.g., as from a Gaussian Process Regression) using the transformations ($f_j(x_i)$) as input variables. This method must be also selected from a set $M = \{ M_1, M_2, M_3, \cdots, M_m \}$ of widely different available methods. The objective is to decide which function transforms each one of the $p$ inputs and which method to use such that $MSE$ is minimum. There are no constraints whatsoever. I think in this case there is no structure to take advantage of since the cost function changes form depending on the choice of the method.
You are probably assuming that the cost function is efficiently computable, so that &quot;does there exist a selection of the $n$ options with less than $c$ cost&quot; is an NP decision problem. This assumption is not actually stated in the original question. The question merely states &quot;The cost function can be any function, not necessarily linear.&quot;
As D.W.'s answer says, &quot;you will need to know something about the cost function and take advantage of some structure or properties it has.&quot; Making the assumption that the cost function can be computed in time polynomial in $n$ gives it a little bit of structure. (Exactly how much structure this gives it is the essence of the P vs. NP problem.)