What does Fagin's result say about NP $\ne$ co-NP?

75 Views Asked by At

I'm no expert in this area, and not trying to solve P vs. NP, just trying to understand a formulation of NP.

It seems like Fagin's result 1974 is saying that NP is the class of structures axiomatizable in existential second-order logic, that is $\Sigma_1^1$. Then co-NP would be $\Pi_1^1$. But I thought that if NP $\ne$ co-NP then P $\ne$ NP. What am I missing?

1

There are 1 best solutions below

10
On BEST ANSWER

P is closed under complementation. If NP $\neq$ co-NP, then NP is not closed under complementation. So then P and NP can't be the same.