<p>Assume we want to find the elements from a set of elements <span class="math-container">$\mathscr{E}$</span> for which all predicates from a set of <span class="math-container">$n$</span> predicates <span class="math-container">$\mathscr{P}$</span> evaluate to true.
In programming terms, we want to compute <code>filter(E, P)</code>.</p>
<p>For each predicate <span class="math-container">$p_i$</span>, let <span class="math-container">$P(p_i)$</span> be the probability of it evaluating to true on a random element from <span class="math-container">$\mathscr{E}$</span> and <span class="math-container">$C(p_i)$</span> as the constant cost of its evaluation.
Assume there is no correlation between the predicate probabilities.</p>
<p>After a predicate fails for an element, no subsequent predicates are going to be evaluated for that element.</p>
<p>To me, it seems that ordering the predicates by nonincreasing <span class="math-container">$C(p_i)/(1 - P(p_i))$</span> and evaluating them in that order will be optimal, as it would be using the most efficient predicates first. Semantically, <span class="math-container">$C(p_i)/(1 - P(p_i))$</span> can be interpreted as the cost per element removed.</p>
<p>However, I not only don't know whether or not this assessment is correct (and the problem is <span class="math-container">$O(n \log n)$</span>), but I also don't know how one would rigorously prove that this ordering is an optimal ordering for minimizing the overall evaluation cost.</p>
<hr />
<p>As requested in the comments, I came across this problem when thinking about the optimal order of filters over a collection of elements. I wondered if I could compute the optimal order if I knew fairly well the probability of the predicates being true and the cost of evaluating each one of them in order to write a more efficient combined filter.</p>
<p>My question already has a <a href="https://cs.stackexchange.com/a/35504/27509">good answer in the CS SE</a>. I didn't know we had two SEs for CS, so I assumed, wrongfully, that TCS (cstheory) was the right board to search for and post my question.</p>

CC BY-SA 4.0
2020-09-04T07:54:08.017Z
This sounds like part of a homework assignment.
Gamow
CC BY-SA 4.0
2020-09-04T14:14:35.713Z
Gamow, I can see why you would say that. I'm not currently enrolled in any educational program. The reason why I requested help with proving that it is O(n log n), if it is, is to prevent someone from simply stating "Yes, sorting by that will be optimal." and not helping me at all with understanding why it is (or isn't) optimal.
Bernardo Sulzbach
CC BY-SA 4.0
2020-09-05T20:36:12.813Z
It would be helpful if you would [edit] your question to credit the original source or describe the context where you encountered this task.
D.W.
CC BY-SA 4.0
2020-09-05T20:37:28.700Z
You ask how to verify that the solution is optimal.  I suggest you first try some examples to see if it always seems to hold (I suggest you code it up and try on many randomly chosen problem instances).  Then, I suggest you try to prove it correct using all the standard approaches to proving correctness of a greedy algorithm -- you can find good explanations of those techniques in standard algorithms textbooks.  This doesn't sound like a research-level question to me.
D.W.
CC BY-SA 4.0
2020-09-05T20:38:57.153Z
See https://cs.stackexchange.com/q/35502/755, https://cs.stackexchange.com/q/59964/755, https://cs.stackexchange.com/q/65284/755, etc.
D.W.
CC BY-SA 4.0
2020-09-06T00:34:26.953Z
@D.W. your links were very useful, thank you. I've also updated my question as you suggested.
Bernardo Sulzbach
<np-hardness>
Is finding the optimal ordering of predicates NP?
Bernardo Sulzbach
# Is finding the optimal ordering of predicates NP?

(Asked by: username_0 on 2020-09-03)

Assume we want to find the elements from a set of elements $\mathscr{E}$ for which all predicates from a set of $n$ predicates $\mathscr{P}$ evaluate to true.
In programming terms, we want to compute `filter(E, P)`.

For each predicate $p\_i$, let $P(p\_i)$ be the probability of it evaluating to true on a random element from $\mathscr{E}$ and $C(p\_i)$ as the constant cost of its evaluation.
Assume there is no correlation between the predicate probabilities.

After a predicate fails for an element, no subsequent predicates are going to be evaluated for that element.

To me, it seems that ordering the predicates by nonincreasing $C(p\_i)/(1 - P(p\_i))$ and evaluating them in that order will be optimal, as it would be using the most efficient predicates first. Semantically, $C(p\_i)/(1 - P(p\_i))$ can be interpreted as the cost per element removed.

However, I not only don't know whether or not this assessment is correct (and the problem is $O(n \log n)$), but I also don't know how one would rigorously prove that this ordering is an optimal ordering for minimizing the overall evaluation cost.

---

As requested in the comments, I came across this problem when thinking about the optimal order of filters over a collection of elements. I wondered if I could compute the optimal order if I knew fairly well the probability of the predicates being true and the cost of evaluating each one of them in order to write a more efficient combined filter.

My question already has a [good answer in the CS SE](https://cs.stackexchange.com/a/35504/27509). I didn't know we had two SEs for CS, so I assumed, wrongfully, that TCS (cstheory) was the right board to search for and post my question.

**Tags:** np-hardness
> **Comments:**
> **username_1**: This sounds like part of a homework assignment.  
> **username_0**: Gamow, I can see why you would say that. I'm not currently enrolled in any educational program. The reason why I requested help with proving that it is O(n log n), if it is, is to prevent someone from simply stating "Yes, sorting by that will be optimal." and not helping me at all with understanding why it is (or isn't) optimal.  
> **username_2**: It would be helpful if you would [edit] your question to credit the original source or describe the context where you encountered this task.  
> **username_2**: You ask how to verify that the solution is optimal.  I suggest you first try some examples to see if it always seems to hold (I suggest you code it up and try on many randomly chosen problem instances).  Then, I suggest you try to prove it correct using all the standard approaches to proving correctness of a greedy algorithm -- you can find good explanations of those techniques in standard algorithms textbooks.  This doesn't sound like a research-level question to me.  
> **username_2**: See https://cs.stackexchange.com/q/35502/755, https://cs.stackexchange.com/q/59964/755, https://cs.stackexchange.com/q/65284/755, etc.  
> **username_0**: @D.W. your links were very useful, thank you. I've also updated my question as you suggested.  

---

## 0 answers

