Why doesn't descriptive complexity theory solve P = NP?
-
04-11-2019 - |
Question
According to the Wikipedia page on Descriptive complexity theory:
In the presence of linear order, first-order logic with a least fixed point operator gives P, the problems solvable in deterministic polynomial time.
Existential second-order logic yields NP, as mentioned above.
If P = NP, wouldn't it be possible to convert any Existential second-order logic into a corresponding first-order logic with a least fixed point operator? That would also imply a bijection between those sets (is there a bijection between existential second-order logic and first-order logic with a least fixed point operator?).
My understanding is first order logic cannot express second-order logic - why doesn't this prove P != NP?
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange