2
$\begingroup$

Suppose I have an array of numbers, and a function boolean isPrime(int n) that I'm allowed to use.

Boolean isPrime(int n) receives a number n and return true if the received number is a prime and false otherwise.

I need to write a function int foo(int[] a) that receives the given array and return the biggest prime number that I can "create" by adding values from the given array.

For example: for the array 8,11,8,2 the function foo should return 19

It's not a homework or something, I noticed that in a lot of job exams there is this type of question. It looks simple and naïve, but it's not.

There are a lot of possibles, for array with size $n$ the are $2^n$ possible combinations. In the given example the possibilities are:$\{8,11,2,8+11,8+8,8+2,8+11+8,\dots\}$

What's the best way to approach this type of question? I'm sure that it's related to some smart algorithm.

$\endgroup$
4
$\begingroup$

The query complexity of your problem, which is the number of oracle calls that any correct algorithm needs to make, is $2^n-1$ (or even $2^n$, if the oracle is allowed to return "No" on all inputs, in which case the answer to your problem is "Infeasible"). This assumes your oracle is a black box. When your oracle is given explicitly, the complexity of the problem could depend on the oracle. For the primality oracle, your problem is likely hard, but this could be challenging to prove since the additive properties of primes are not well-understood.

Indeed, suppose that you have an algorithm solving your problem on arrays of length $n$ using less than $2^n-1$ oracle calls in the worst case. Run it on the array $1,2,4,\ldots,2^{n-1}$. Whenever the oracle asks a question, always return "No" (i.e., cannot be used). When the algorithm has finished, there are at least two sets $S,T$ that have not been queried. There we can consider two oracles, one that says "Yes" only on $\Sigma(S)$ (the sum of elements in $S$) and the other that says "Yes" only on $\Sigma(T)$. By construction, $\Sigma(S) \neq \Sigma(T)$, and so the correct answer is different in both cases. However, the algorithm cannot distinguish between the two oracles, and so its output will be wrong for at least one of these two oracles.

If we allow the oracle to return "No" on all inputs, then we can get a contradiction even given an algorithm that makes exactly $2^n-1$ oracle calls in the worst case. Running it on the same array and answering every query negatively, there is always a set $S$ which has not been queried, and the algorithm cannot distinguish between the oracle which answers "Yes" only on $S$ (in which case the answer is $S$) and the oracle which always answers "No" (in which case the answer is "Infeasible").

$\endgroup$
  • $\begingroup$ "Oracle calls" had me irritated for a moment. $\endgroup$ – greybeard Dec 25 '17 at 16:05

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.