A Specialization of Cook's Conjecture

martdowd at aol.com martdowd at aol.com
Sat Mar 21 13:02:30 EDT 2020


I have just completed a new complexity theory paper,
  ``A Specialization of Cook's Conjecture''
available at
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>

More information about the FOM mailing list