We give a complete characterisation of the single and double arrow relations of the standard context K ( L n ) of the lattice L n of partitions of any positive integer n under the dominance order, thereby addressing an open question of Ganter, 2020/2022. • Type D partitions allow up-arrows, which fail to be down-arrows, to all types I–IV. • Type IV partitions allow down-arrows, which fail to be up-arrows, to all types A–D. • Type D partitions have double arrows only to those of type IV and vice versa. • Partitions of types A–C are double arrow related only to types I–III and vice versa. • For n ≥ 3 there are exactly 2 n − 4 one-generated arrow-closed ( 1 × 1 ) -subcontexts of K ( L n ) .

We investigate the complexity of three optimization problems in Boolean propositional logic related to information theory: Given a conjunctive formula over a set of relations, find a satisfying assignment with minimal Hamming distance to a given assignment that satisfies the formula ( NearestOtherSolution , NOSol ) or that does not need to satisfy it ( NearestSolution , NSol ). The third problem asks for two satisfying assignments with a minimal Hamming distance among all such assignments ( MinSolutionDistance , MSD ). For all three problems we give complete classifications with respect to the relations admitted in the formula. We give polynomial time algorithms for several classes of constraint languages. For all other cases we prove hardness or completeness regarding APX, poly-APX, or equivalence to well-known hard optimization problems.

We consider finitary relations (also known as crosses) that are definable via finite disjunctions of unary relations, i.e. subsets, taken from a fixed finite parameter set Γ. We prove that whenever Γ contains at least one non-empty relation distinct from the full carrier set, there is a countably infinite number of polymorphism clones determined by relations that are disjunctively definable from Γ. Finally, we extend our result to finitely related polymorphism clones and countably infinite sets Γ. These results address an open problem raised in Creignou, N., et al. Theory Comput. Syst. 42 (2), 239–255 ( 2008 ), which is connected to the complexity analysis of the satisfiability problem of certain multiple-valued logics studied in Hähnle, R. Proc. 31st ISMVL 2001, 137–146 ( 2001 ).