Pago, Benedikt
Choiceless Computation and Symmetry: Limitations of Definability
Abstract
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 isomorphisminvariant computation model working with hereditarily finite sets as data structures. While it is easy to check that the evaluation of CPTsentences is possible in polynomial time, the converse has been open for more than 20 years: Can every PTIMEdecidable 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 superpolynomially 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 socalled CaiFürerImmerman (CFI) problem is one of the standard "benchmarks" for logics and maybe best known for separating fixedpoint 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 PTIMEproblem which provably cannot be tackled with the stateoftheart choiceless algorithmic techniques.
BibTeX  Entry
@InProceedings{pago:LIPIcs:2021:13467,
author = {Benedikt Pago},
title = {{Choiceless Computation and Symmetry: Limitations of Definability}},
booktitle = {29th EACSL Annual Conference on Computer Science Logic (CSL 2021)},
pages = {33:133:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771757},
ISSN = {18688969},
year = {2021},
volume = {183},
editor = {Christel Baier and Jean GoubaultLarrecq},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13467},
URN = {urn:nbn:de:0030drops134673},
doi = {10.4230/LIPIcs.CSL.2021.33},
annote = {Keywords: finite model theory, descriptive complexity, choiceless computation, symmetries of combinatorial objects}
}
13.01.2021
Keywords: 

finite model theory, descriptive complexity, choiceless computation, symmetries of combinatorial objects 
Seminar: 

29th EACSL Annual Conference on Computer Science Logic (CSL 2021)

Issue date: 

2021 
Date of publication: 

13.01.2021 