We know $NP \neq P$ from a lot of point of view like empirical reason,or theoretical reasons such as finite model theory or descriptive complexity.Although we find so many reasons to believe $NP \neq P$,we have not found any proof for it now.

So any reason to believe that $NP \neq P$ is unprovable in ZFC?Any result about unprovability of $NP \neq P$ in ZFC or weaker system than ZFC.

  • 7
    $\begingroup$ Decade out of date: Aaronson, Scott. "Is P versus NP formally independent?." Bulletin of the EATCS 81 (2003): 109-136. (PDF download link). Or better: Quantum Computing Since Democritus. $\endgroup$ – Joseph O'Rourke Sep 11 '14 at 0:48
  • $\begingroup$ @JosephO'Rourke,thank you for the reference.It seems that the critical hard part for a proof is relating bound,usually,problems about bound in math is hard. $\endgroup$ – XL _At_Here_There Sep 11 '14 at 1:00
  • 2
    $\begingroup$ Your spacing is off. You want not $NP! = P$ but rather $NP\;{!\!=}\;P$ ... or (for mathematicians) even better $NP \ne P$. $\endgroup$ – Gerald Edgar Sep 11 '14 at 1:03
  • $\begingroup$ @GeraldEdgar,thank you very much ,I will edit it. $\endgroup$ – XL _At_Here_There Sep 11 '14 at 1:06

Your Answer

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

Browse other questions tagged or ask your own question.