provability of P=NP

martdowd at martdowd at
Fri Feb 21 20:55:33 EST 2020


I have just completed a complexity theory paper,
  "On the provability of P=NP"
available at
Following is the abstract.

In \cite{Will19} Williamson shows that it follows in ZFC from a statement
which is independent of ZFC, that some instances of the subset sum problem
can be solved in polynomial time.  He goes on to suggest that P=NP might
not be provable in ZFC.  Here we argue that as of present knowledge,
it doesn't seem any easier to prove that P=NP is unprovable in
polynomial time arithmetic, than it is to prove P$\neq$NP.

The last section contains some conjectures, updating material in my PhD
thesis, which imply NP$\neq$Co-NP or P$\neq$NP.

Martin Dowd

-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20200222/b93a9ce8/attachment.html>

More information about the FOM mailing list