Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site cornell.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!mhuxt!houxm!mtuxo!mtunh!mtung!mtunf!ariel!vax135!cornell!rance
From: rance@cornell.UUCP (W. Rance Cleaveland)
Newsgroups: net.math
Subject: Re: Logic (for logicians)
Message-ID: <3313@cornell.UUCP>
Date: Tue, 23-Jul-85 11:13:38 EDT
Article-I.D.: cornell.3313
Posted: Tue Jul 23 11:13:38 1985
Date-Received: Thu, 25-Jul-85 06:19:12 EDT
References: <456@ttidcc.UUCP> <457@ttidcc.UUCP> <1586@hao.UUCP>
Organization: Cornell Univ. CS Dept.
Lines: 18

> This is probably getting way too technical, but the statement in <3033@cornell>
> that complexity theory has nothing to do with logic is false ( Didn't Juris 
> teach you that at Cornell ? :-) ). 
> 
> In fact, the historic paper by Cook on NP is called
> "The complexity of theorem-proving procedures". More to the point, a complete
> problem for co-NP (languages with their complement in NP) is to decide whether
> a boolean formula is a tautology.

Hmm.  I think you misunderstood my remarks about the connection between
logics and complexity (maybe I wasn't as clear as I could have been).  My point
was that the question of constructive vs classical logic has no real con-
nection with complexity theory.  There are certainly many interesting problems
in classical (i.e. truth-valued) logic which have implications in complexity
theory (and yes, we learn all about them at Cornell)....

Regards,
Rance Cleaveland