Skip to main content
2 votes

Why is order/choice an issue for a logic for PTIME

But what would be the issue if we extended IFP to just have an order and made it that a structure satisfies a formula if it satisfies for an arbitrary order? If done this way, it is difficult to see ...
Reijo Jaakkola's user avatar
1 vote

Why is order/choice an issue for a logic for PTIME

My interpretation of your question is something along the lines of, "why should we care whether there is a logic that captures PTIME?" This is a fair question: there are good reasons for ...
Siddharth's user avatar
  • 841
1 vote

Why is order/choice an issue for a logic for PTIME

If you treat an integer in terms of, say, it's binary expansion, and the FO structure you use for that is a single unary relation on a set of size n (indicating which bits of your length-n string are ...
Joshua Grochow's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible