A Specialization of Cook's Conjecture

[martdowd at aol.com]

FOM:

I have just completed a new complexity theory paper,
  ``A Specialization of Cook's Conjecture''
available at
  https://www.researchgate.net/publication/340083150
Following is the abstract.

In \cite{Co75} Cook conjectures that the representing formulas for the
consistency of polynomial time arithmetic do not have polynomial length
extended resolution proofs.  It is known that such proofs do not exist,
provably in polynomial time arithmetic.  This question can be specialized,
to ask whether such proofs can be shown to exist, in even very mild
extensions of polynomial time arithmetic.
Results here suggest that it might be no easier to prove that they don't
than the full conjecture.

Martin Dowd

-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20200321/9a63aa84/attachment.html>