Towards Capturing Order-Independent P
summary
Asks whether all polynomial-time graph properties that ignore vertex order—order-independent P—have a clean logical description. Gives the concrete negative: the CFI gadget (the CFI construction) yields a family that defeats fixpoint with counting unless one allows a linear number of variables, so FPC cannot express that parity-style property. Notes positive results: FPC captures P on many restricted classes (excluded-minor, planar) and that adding operations (matrix rank, or choiceless PTime) can express the CFI property, but full equivalence with order-independent P remains open.
AI-written summary · about