Home Online Mathematical Communication Computational Complexity More on Psuedodeterminism

More on Psuedodeterminism

Computational Complexity 2023-07-19

Back in May I posted about a paper that finds primes pseudodeterministically and Quanta magazine recently published a story on the result. Oddly enough the paper really isn't about primes at all.

Consider any set A such that 

  1. A is easy to compute, i.e., A is in P.
  2. A is very large, that is there is a c such that for all n, the number of strings of length n is at least 2n/nc. If you throw a polynomial number of darts you are very likely to hit A.
Chen et al show that for any such A, there is a probabilistic polynomial time Turing machine M such that for infinitely many x, M on input 1|x| will output x with high probability. 
The set of primes has property 1 by Agrawal, Kayal and Saxena and property 2 by the prime number theorem. Why focus the paper on primes though? Because deterministic prime number finding is a long-standing open problem and there aren't many other natural problems that have properties 1 and 2 where we don't know easy deterministic algorithms to find examples.
With the general result, we can think about oracle results. It's pretty easy to create an A, such that A has property 2 and no deterministic polynomial-time algorithm with oracle access to A can find an element of length n on input 1n for infinitely many n. Since A is always in PA we get property 1 for free. That would suggest to push the result to finding primes deterministically would require using properties of the primes beyond being large and easy. 
Maybe not. Rahul Santhanam, one of the authors, tells me their proof doesn't relativize, though whether the result relativizes is an open question, i.e. whether there is an A fulfilling property 2 such that any pseudodeterministic algorithm with oracle access to A will fail to find more than a finite number of elements of A. It does seem hard to construct this oracle, even if we just want the pseudodeterministic algorithms to fail for infinitely many n. 
Nevertheless it seems unlikely you'd be able to use these techniques to prove a deterministic algorithm for all large easy A. If you want to find primes deterministically you'll probably need some to prove some new number theory.