Choiceless Polynomial Time, Symmetric Circuits and Cai-Fürer-Immerman Graphs

Benedikt Pago

Choiceless Polynomial Time (CPT) is currently the only candidate logic for capturing PTIME (that is, it is contained in PTIME and has not been separated from it). A prominent examp…