3 ms·

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.