3 ms·

If you approach it from Fagin’s Theorem, which provides that NP == the set of existential second order boolean queries, NP = SO∃. Even when the first order part

If you approach it from Fagin’s Theorem, which provides that NP == the set of existential second order boolean queries, NP = SO∃. Even when the first order part is universal...you will see how the P=NP question will probably never be solved. To be clear, we absolutely need optimists to keep looking at it and learning more. But the way it is taught often makes it seem like proving or disproving P=NP is just a matter of time, when the safe bet is that it will never be solved.

mehulashah 2y ago
I don’t understand this. Can you give me some pointers so I can research it myself?
- nyrikki 2y ago
  Look at the SO entry on complexity zoo. existential quantifier: “there exists an x such that...” universal quantifier: “for every x such that..." NP is the truthyness of yes-instances co-NP is the truthyness of no-instances P=co-P but we think NP!=co-NP NP is the same as a second order logic with an existential second order part. co-NP is the same as second order logic with a universal second order part. Consider how the following two are different: “there exists an x such that there exists a y such that...” “there exists an x such that for every y such that...” That is an oversimplified bad example, but set theory, logic, and complexity are were to start. Gödel is another lens, but the difference between syntactic and symantic completeness causes problems. As well as Gödel dealing with TMs and not the physically unrealizable NTM. Proving P=NP would have the implication that NP=co-NP Proving P!=NP would prove the opposite. IMHO the most likely lottery winning outcome is that we prove that we can't prove P=NP, but that would cause other issues. More likely we will have to accept the limits of computable proofs and have an unsatisfying result and the problem will stay open.

mehulashah 2y ago

I don’t understand this. Can you give me some pointers so I can research it myself?

nyrikki 2y ago
Look at the SO entry on complexity zoo. existential quantifier: “there exists an x such that...” universal quantifier: “for every x such that..." NP is the truthyness of yes-instances co-NP is the truthyness of no-instances P=co-P but we think NP!=co-NP NP is the same as a second order logic with an existential second order part. co-NP is the same as second order logic with a universal second order part. Consider how the following two are different: “there exists an x such that there exists a y such that...” “there exists an x such that for every y such that...” That is an oversimplified bad example, but set theory, logic, and complexity are were to start. Gödel is another lens, but the difference between syntactic and symantic completeness causes problems. As well as Gödel dealing with TMs and not the physically unrealizable NTM. Proving P=NP would have the implication that NP=co-NP Proving P!=NP would prove the opposite. IMHO the most likely lottery winning outcome is that we prove that we can't prove P=NP, but that would cause other issues. More likely we will have to accept the limits of computable proofs and have an unsatisfying result and the problem will stay open.