Choiceless Polynomial Time with Witnessed Symmetric Choice
Moritz Lichter, Pascal Schweitzer · 2022
We extend Choiceless Polynomial Time (CPT), the currently only remaining promising candidate in the quest for a logic capturing Ptime, so that this extended logic has the following property: for every class of structures for which isomorphism is definable, the logic automatically captures Ptime.