provability of P=NP
martdowd at aol.com
martdowd at aol.com
Fri Feb 21 20:55:33 EST 2020
FOM:
I have just completed a complexity theory paper,
"On the provability of P=NP"
available at
https://www.researchgate.net/publication/339426546
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