FOM: a "hard" problem?

[JoeShipman@aol.com]

In a message dated Wed, 12 Jul 2000 12:23:26 PM Eastern Daylight Time, Harvey Friedman <friedman at math.ohio-state.edu> writes:

<<< PROBLEM: Is the number of primes less than 2^100 even? Is the number of
primes less than 2^10,000 even?

I am under the impression that such problems are completely hopeless, even
with the aid of a computer. Hopeless, even if we wish to prove or refute it
with a high degree of certainty. Hopeless even to justify making a
conjecture as to whether it is true or false.

But should we conjecture some sort of formal undecidability of this
question? E.g.,

CONJECTURE?? The version with 2^10,000 cannot be proved or refuted in ZFC
with abbreviations without using more than 2^100 bits.>>>


Because it is conceivable that some analytic approximation to the pi(x) function may be found which is calculable in polynomial time in the input size, a better example would use 2^2^10000  rather than 2^10000.
In fact, if P=PSPACE, an open question, then the number of primes less  than 2^n, and hence the parity of this number, is going to be calculable in time polynomial in n.

If you don't want to have infeasible numbers as part of the problem statement, a better bet for a "hard" problem would be the parity of some reasonable-sized Ramsey number like R(10,10), because good approximations for R(n,n) seem much harder than good approximations to pi(n), though I don't think we'd be able to prove that such a problem was hard for the same reason (solvable in PSPACE).

-- Joe Shipman