<p>Given a univariate polynomial of the form <span class="math-container">$p(x) = \prod_{0 \leq i \leq N}{(x*a_i + b_i)}$</span> when all of the <span class="math-container">$a_i$</span> and <span class="math-container">$b_i$</span> are numbers in the range [-1,1] and <span class="math-container">$i$</span> goes from <span class="math-container">$0$</span> to <span class="math-container">$N$</span> (we are given all the values <span class="math-container">$a_i$</span> and <span class="math-container">$b_i$</span> as part of the polynomial).</p>
<p>I am interested in the range <span class="math-container">$0 \leq x \leq 1$</span>.
Assuming that in this range the polynomial is getting maximum when <span class="math-container">$x$</span> is in the range [0,0.5], what is the complexity of finding a maximal subset <span class="math-container">$S$</span> of the set <span class="math-container">${0... N}$</span> such that new polynomial <span class="math-container">$p'(x) = \prod_{i \in S}{(x*a_i + b_i)}$</span> will get a maximum value in the range [0.5,1]? (Or to determine that there is no such subset).
(or vice versa, if the polynomial is getting maximum in the range [0.5,1], we need to find maximal subset that will make it get a maximum value in the range [0,0.5]).</p>
<p>Thanks!</p>

CC BY-SA 4.0
2023-08-29T21:37:36.343Z
Sorry, I do not understand. If $N=0$ and $a_0 = 1$ and $b_0 = 0$, the polynomial is $p(x) = x$, and in the range $0 \leq x \leq 1$ the maximum is achieved when $x=1$, not when $x$ is in the range [0, 0.5]. Or did you write "Given the fact that ..." to mean "Assuming that ..."?
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2023-08-29T23:57:19.947Z
Thanks!
I made an error in the question (the goal is to find maximal subsets and not minimal).
I was confused since I was used to seeing it as "finding minimal subsets to remove", but this is equivalent.
Amit Bergman
CC BY-SA 4.0
2023-08-30T03:48:30.140Z
OK, thanks! I must confess the problem does not look too natural to me however, maybe it would help to give some more context or motivation (why this problem, why this form of polynomial, why the intervals [0, 0.5] and [0.5, 1]...), or some approaches that you already tried, some properties of the problem (i.e., is it the same to look for maximal or maximum, is the property that you want monotone over the set S). BTW, do constant polynomials "get maximal" at a specific point? (e.g., N=0 and a_0 = 0) Other than this maybe someone more specialized than me can answer!
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2023-08-30T09:04:56.667Z
The title says *minimal* subset, the post body says *maximal* subset. Which it is? Also, you mean minimal/maximal with respect to inclusion, or with respect to cardinality?
Emil Jeřábek
CC BY-SA 4.0
2023-08-31T00:45:55.483Z
Thanks! 
I want to find the minimal subset that removing it will change the argmax, or the maximal subset that keeping it will change the argmax (equivalent of course).
Amit Bergman
CC BY-SA 4.0
2023-08-31T00:47:08.963Z
The context is that each term in the polynomial corresponds to a data point in my data, the polynomial is the likelihood of the  data, and I want to find a subset that removing it from the data will change the place where the likelihood function is getting its maximum value.
Amit Bergman
<np-hardness><polynomials><complexity>
Hardness of finding minimal subsets that will change the maximum of a univariate polynomial
Amit Bergman
# Hardness of finding minimal subsets that will change the maximum of a univariate polynomial

(Asked by: username_0 on 2023-08-29)

Given a univariate polynomial of the form $p(x) = \prod\_{0 \leq i \leq N}{(x\*a\_i + b\_i)}$ when all of the $a\_i$ and $b\_i$ are numbers in the range [-1,1] and $i$ goes from $0$ to $N$ (we are given all the values $a\_i$ and $b\_i$ as part of the polynomial).

I am interested in the range $0 \leq x \leq 1$.
Assuming that in this range the polynomial is getting maximum when $x$ is in the range [0,0.5], what is the complexity of finding a maximal subset $S$ of the set ${0... N}$ such that new polynomial $p'(x) = \prod\_{i \in S}{(x\*a\_i + b\_i)}$ will get a maximum value in the range [0.5,1]? (Or to determine that there is no such subset).
(or vice versa, if the polynomial is getting maximum in the range [0.5,1], we need to find maximal subset that will make it get a maximum value in the range [0,0.5]).

Thanks!

**Tags:** np-hardness, polynomials, complexity

> **Comments:**
> **username_1**: Sorry, I do not understand. If $N=0$ and $a_0 = 1$ and $b_0 = 0$, the polynomial is $p(x) = x$, and in the range $0 \leq x \leq 1$ the maximum is achieved when $x=1$, not when $x$ is in the range [0, 0.5]. Or did you write "Given the fact that ..." to mean "Assuming that ..."?  
> **username_0**: Thanks! I made an error in the question (the goal is to find maximal subsets and not minimal). I was confused since I was used to seeing it as "finding minimal subsets to remove", but this is equivalent.  
> **username_1**: OK, thanks! I must confess the problem does not look too natural to me however, maybe it would help to give some more context or motivation (why this problem, why this form of polynomial, why the intervals [0, 0.5] and [0.5, 1]...), or some approaches that you already tried, some properties of the problem (i.e., is it the same to look for maximal or maximum, is the property that you want monotone over the set S). BTW, do constant polynomials "get maximal" at a specific point? (e.g., N=0 and a_0 = 0) Other than this maybe someone more specialized than me can answer!  
> **username_2**: The title says *minimal* subset, the post body says *maximal* subset. Which it is? Also, you mean minimal/maximal with respect to inclusion, or with respect to cardinality?  
> **username_0**: Thanks!  I want to find the minimal subset that removing it will change the argmax, or the maximal subset that keeping it will change the argmax (equivalent of course).  
> **username_0**: The context is that each term in the polynomial corresponds to a data point in my data, the polynomial is the likelihood of the  data, and I want to find a subset that removing it from the data will change the place where the likelihood function is getting its maximum value.  

---

## 0 answers

