This question comes from an application in multivalued logic.
Suppose, we are given an alphabet of three letters $A, B, C$ and a set of indices $1,2,3,4,5$. Consider items formed by subscripting the letters with one of the indices. Examples are the following:
$$A_1 \\ B_4 \\ C_3 \\ ... $$
Suppose, additionally, that there is a total binary relation $\mathcal{R}$ on items $*_i <= *_j$ for each pair $ i, j \in \{ 1,..., 5 \} $ where $*$ denotes one of the letters $A,B$ and $C$. The relation is reflexive and transitive.
Consider a set of strings of length $5$ freely generated by the alphabet $A, B, C, ...$ disregarding ordering. Examples are the following:
$$ AABBC \\ AAAAB \\ AABCC \\ ... $$
Since order doesn't count, a string $AABBC$ is the same as $ABBAC$.
Let's call such strings templates. The templates can be "filled in" with the indices to form tuples of items using the following rules:
- R1: there may be no repetitions of indices disregarding the letter type, e.g.
$$A_1, A_1, B_2, C_3, C_4$$
and
$$A_1, A_2, B_2, C_1, C_4$$
are both forbidden since the index $1$ is used two times.
- R2: ordering in a tuple does not count, e. g.
$$\left( A_3 A_2 B_1 B_4 C_5 \right)$$
is the same as
$$\left( A_2 A_3 B_1 B_4 C_5 \right)$$
One can think of such "filling in" the templates as filling in a truth table with several logical levels in general.
Let us denote the set of all freely generated strings of length $5$ from the $A,B$ and $C$ by $\mathbb{Tmp}$. Let $\mathbb{Tpl}$ denote the set of all tuples generated by index assignments according to the rules R1 and R2. We can define a mapping $U:\mathbb{Tpl} \mapsto \mathbb{Tmp}$ which removes the indices from a tuple and gives its underlying template. For example:
$$ U \left( A_2 A_3 B_1 B_4 C_5 \right) = AABBC $$
We say that a tuple $T$ satisfies the template $t$ if $U(T) = t$. We say that $T$ satisfies a set of templates $\tau = \left(t_1, t_2, ..., t_l \right)$ if there exists a template $t_i \in \tau$ for some $i \in \left( 1,2,...,l \right)$ s. t. $U(T) = t_i$.
Suppose, that we are given a set of templates $\tau$ and a total binary relation $\mathcal{R}$ on items.
What is the greatest item (greatest in the sense of the binary relation $\mathcal{R}$) of all the least items of all the tuples satisfying the templates $\tau$. In other words, what is the maximin item of the tuples?
The bruteforce algorithm is evident: take a template, build all the corresponding tuples, compare elements in each tuple and find the least, compare all the outcomes of the previous step, take the greatest. I am sure this is an $NP$-complete problem if the underlying truth table is irreducible.
What if we order all the items to obtain a sequence like this:
$$ C_2 <= B_4 <= C_1 <= C_5 <= B_1 <= A_2 <= C_3 <= A_3 <= B_3 <= C_4 <= A_4 <= A_5 <= B_5 <= A_1 <= B_2$$
Let's call this sequence $S$.
Can it simplify the problem by any chance?
For instance, consider the templates:
$$\tau = \left( AAAAB, AAABB, AAABC \right)$$
Can there be an algorithm more effective than the bruteforce? I was thinking in the following way: one can start in the sequence $S$ form left to right and "drop" items until there is no more letters to drop (otherwise, the templates are violated) or if the indexing requirement is violated.
Example of such a procedure goes like this:
drop $C_2$, drop $B_4$, drop $C_1$, drop $C_5$, drop $B_1$, drop $A_2$, drop $C_3$, drop $A_3$, $B_3$ must be picked
So no tuple may contain an item greater than $B_3$.
It seems to offer a minor complexity reduction and only for simple templates. For more complex ones, there are subtleties which I won't discuss here. But I am suspicious that there is a fundamental limitation in this problem which makes every algorithm not really better than the bruteforce.
