  The search for a logic capturing PTIME is a long standing open problem in
finite model theory. One of the most promising candidate logics for this is
Choiceless Polynomial Time with counting (CPT). Abstractly speaking, CPT is an
isomorphism-invariant computation model working with hereditarily finite sets
as data structures. While it is easy to check that the evaluation of
CPT-sentences is possible in polynomial time, the converse has been open for
more than 20 years: Can every PTIME-decidable property of finite structures be
expressed in CPT? We attempt to make progress towards a negative answer and
show that Choiceless Polynomial Time cannot compute a preorder with colour
classes of logarithmic size in every hypercube. The reason is that such
preorders have super-polynomially many automorphic images, which makes it
impossible for CPT to define them. While the computation of such a preorder is
not a decision problem that would immediately separate P and CPT, it is
significant for the following reason: The so-called Cai-F\"urer-Immerman (CFI)
problem is one of the standard benchmarks for logics and maybe best known for
separating fixed-point logic with counting (FPC) from P. Hence, it is natural
to consider this also a potential candidate for the separation of CPT and P.
The strongest known positive result in this regard says that CPT is able to
solve CFI if a preorder with logarithmically sized colour classes is present in
the input structure. Our result implies that this approach cannot be
generalised to unordered inputs. In other words, CFI on unordered hypercubes is
a PTIME-problem which provably cannot be tackled with the state-of-the-art
choiceless algorithmic techniques.
