2
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

Note the difference between second-order logic, and existential second order logic. Full logic is much more powerful than existential logic.

Also, it's important not to underestimate the power of a least-fixed point operator. Linearly-ordered first order logic is likely far less powerful than the version with fixed-points.

In short, we know that vanilla first-order logic is weaker than vanilla second-order logic, but we don't know that linearly-ordered first order logic with a least-fixed point operator is weaker than the existential fragment of second order logic.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.