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 pickedSo 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.
Optimization in multivalued logic. Optimal strings with given patterns
algorithms;complexity theory;time complexity;np complete;kolmogorov complexity