We study constraint satisfaction problems of non-rigid structures in a finite and omega-categorical setting. We show that not having a binary essential polymorphism is a sufficient criterion for NP-hardness of the constraint satisfaction problem of a (model-complete) core, as long as its automorphism group is not the free action of a Boolean group. To understand the behaviour of low arity polymorphisms, we classify the possible types of minimal operations above an arbitrary permutation group. In this, we generalise a classical theorem of Rosenberg above the trivial group, and significantly improve a result of Bodirsky and Chen above the automorphism groups of omega-categorical structures. Finally, we answer three questions of Bodirsky on binary polymorphisms of infinite templates for constraint satisfaction problems.

Abstract A recent article of Chernikov, Hrushovski, Kruckman, Krupinski, Moconja, Pillay, and Ramsey finds the first examples of simple structures with formulas which do not fork over the empty set but are universally measure zero. In this article we give the first known simple $\omega $ -categorical counterexamples. These happen to be various $\omega $ -categorical Hrushovski constructions. Using a probabilistic independence theorem from Jahel and Tsankov, we show how simple $\omega $ -categorical structures where a formula forks over $\emptyset $ if and only if it is universally measure zero must satisfy a stronger version of the independence theorem.