principleMinor
Why doesn't descriptive complexity theory solve P = NP?
Viewed 0 times
whytheorydoesnsolvecomplexitydescriptive
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#84673, answer score: 8
Revisions (0)
No revisions yet.