FOM: Clarification to my Pi^0_2 comment:

[Soren Riis]

--------------------------------------
Clarification to my Pi^0_2 comment:
--------------------------------------
On reflection I realize that my comment on 
Pi^0_2-conjectures [Riis; 19/4/98] was confusing 
and could be misunderstood. For a given Pi^0_2 
conjecture B one can of course "conjecture" it is 
provable in some specific subsystem of ZFC. This 
"conjecture" could then be expressed as a purely 
existential conjecture. I did not intend to claim 
that any conjecture follows from a "plausible" 
stronger, but purely existential conjecture. 

The (very elementary) point I was trying to make 
concerns "real life" Pi^0_2-conjectures. Consider 
for example the conjecture P \neq NP. This sentence is 
although certainly Pi^0_2 in some very strong sense 
close in being Pi^0_1.

The reason is that we actually expect P to be quite 
different from NP and it seems reasonable that any 
algorithm running in time n^k, and having program 
size s, are doomed to fail deciding the satisfiability 
problem already for satisfiability problems of size 
\leq Q(k)+ log(s) where Q is some low degree polynomial. 

All algorithms running in time n^1000 will probably 
already fail on input of size (1,000)^2= 1,000,000. 
Provided of course we do not build in some huge 
database (of size of order 2^1,000,000) into the 
program. Well of course we do not know whether they will 
all fail. Perhaps n^k programs first must fail for 
inputs of size F_{\epsilon_0}(k)+s in which case the 
P \neq NP of course would be independent of PA.

Now P \neq NP might or might not be probable in PA 
(or ZFC). This I have virtually no intuition about. 
However I will certainly strongly support that:

(*) "all algorithms with program size s and running in 
time n^k will fail deciding the satisfiability problem 
for some inputs of size \leq 2^k+s+1,000". 

The elementary point I was trying to make is that though 
the exponential function does not belong to the language 
L=L(0,1,+,\cdot) of arithmetic, we can rephrase (*) 
[which are of the form \forall x \exists y<F(x) A(x,y)] 
and write it as the Pi^0_1 sentence

\forall x,z \exists y \leq z ("F^{-1}z \leq x" or A(x,y))

where "F^{-1}z \leq x" is expressed by a bounded formula 
in the language L. 

So P \neq NP is "essentially" Pi^0_1. What about the 
Poincare conjecture and other Pi^0_2 conjectures? I
would expect them to be "essential" Pi^0_1, but I could
of course be mistaken.

Søren Riis