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
scroll top