5
$\begingroup$

I will start of with an informal example and give a more formal problem definition later.

Say I have a finite set of positive real values: $\{2.3, \pi, 4.382, 0.3\}$. Using normal addition and multiplication, we can construct expressions like $(\pi + 2.3) * 0.3 + 4.382$ and $(0.3 + \pi) * (2.3 + 4.382)$. We put the following constraints on the expressions:

  1. Each value in the set must be used exactly once in the expression.
  2. We can only use addition, multiplication and brackets in our expression.

The goal now is to get as close to a target value, say $9.5$. For example, the expression $2.3 * \pi * 4.382 * 0.3 = 9.49886...$ gets close. How can we find the expression whose evaluation is closest to $9.5$? Or more formally:

Given a finite set $V$ of - not necessarily unique - elements, two binary operands $f(x, y)$ and $g(x, y)$ that operate on the elements in $V$ and a target value $t$, find the expression $E$ containing each element of $V$ exactly once, such that the evaluation of $E$ is as close to $t$ as possible. $E$ must consist only of the values in $V$, the given operands and brackets.

I understand that for small sets, an exhaustive check that checks all possible expressions is feasible. Using heuristics, quickly finding an approximate answer (with small distance to the target) is probably possible for larger sets too. My questions are; does a more efficient method exist to find exact answers for large sets? Do efficient methods exist specifically for certain operands? What fields of mathematics and computer science touch on this subject?

$\endgroup$
  • $\begingroup$ Can you provide some motivation for this problem? Is this a theoretical exercise or do you have real data for which you are trying to solve? $\endgroup$ – Nicholas Mancuso Nov 3 '16 at 19:04
  • 1
    $\begingroup$ @NicholasMancuso I was inspired by a game I once played where you roll dice and try to get as close to a target score as possible using basic arithmetic. This is a generalization of that problem. The number of operands could be more than two, but I wanted to keep the generalization relatively simple. $\endgroup$ – Arthelais Nov 3 '16 at 19:08
2
$\begingroup$

This is a very difficult problem. For an already hard special case, you can look at the subset sum problem. So in general, one direction to look at is NP-hard optimization problems (and ways of coping with hardness).

$\endgroup$
  • $\begingroup$ Thank you, after reading about the subset sum problem and similar ones, I'm convinced you are correct. $\endgroup$ – Arthelais Nov 3 '16 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.