TransWikia.com

Which class does this NP problem belong to?

Computational Science Asked on February 25, 2021

Suppose $n$ inputs ($x_1, x_2, x_3, cdots, x_n$) can take on any of $m$ values, say ${ k_1, k_2, k_3, cdots, k_m }$, and that there is a cost function $y = f(x_1, x_2, x_3, cdots, x_n)$. For instance, for $n = 3$ ($x_1, x_2, x_3$) and $m = 2$ (${ k_1, k_2 }$) we have a total of $8$ possible triplets $S = { (k_1k_1k_1), (k_1k_1k_2), (k_1k_2k_1), (k_1k_2k_2), (k_2k_1k_1), (k_2k_1k_2), (k_2k_2k_1), (k_2k_2k_2) }$. The objective is to find the triplet that minimizes $y$ without enumerating all possibilities.

I tried to relate this NP problem to various problems in combinatorial optimization (e.g., TSP, 0/1 Knapsack, Assignment Problem, etc.), but found none that could barely resemble it.

Which class does this NP problem belong to?

EDIT: The problem I have at hand is a regression problem where each of $n$ inputs, $x_1, x_2, x_3, cdots, x_n$, needs to undergo a variable transformation using one of $q$ basis 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}{p} sum_{k=1}^p (y_k – hat{y}_k)^2$, where $p$ 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 $n$ inputs and which method to use such that $MSE$ is minimum. There are no constraints whatsoever.

Any advise would be much appreciated.

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP