[FOM] Questions on Complexity Theory

[Dmytro Taranovsky]

Does LogSpace = PP ?
Is integer factorization ExpTime complete?
Does LTime = LSpace?

(At most one of the above is true.)
If LTime = LSpace, what if we use function problems (output same length
as input) instead of decision problems?

PP is the complexity class of problems for which a guess (slightly) more
likely than not to be correct can be made in polynomial time (with the
help of a random number generator).  PP includes NP and BQP.
LSpace refers to linear space.  Problems in computers science tend to be
in LSpace.
LTime, linear time, refers to time O(n log n) (and space O(n)) for
(single head with input given on the work tape) Turing machines on
binary trees.

Linear in LTime refers to linearity with respect to time it takes to
copy the data or test for string equality.  By the way, does LTime =
quadratic time for standard (single-head) Turing machines?  That would
confirm that LTime is true linear time.

Had we defined LTime as linear time on dual-head Turing machines on a
two-dimensional tape, would we have a proof that LTime < LSpace (at
least for function problems and non-deterministic space)?

What time lower bounds have been proved for purported LogSpace solutions
for NLIN (non-deterministic linear time) complete problems?  

At present we simply do not have the methods to disprove the equalities
above.  The three main methods are constructive reduction (ex. Primes is
in P, PSpace = NPSpace), diagonalization (ex. LTime < P, LogSpace <
LSpace), and communication complexity (ex. testing for string equality
requires quadratic time for standard Turing machines).

The consensus view is that the complexity classes like P and NP are
different, but that proving the inequalities requires a breakthrough in
the theory of knowledge and computation.  An alternative view is that
the classes have completely resisted proof of inequality because
canonical complexity classes are in fact comparable and that likely
LTime = LSpace.

We actually have candidate "efficient" (note the quotes) algorithms for
LSpace (and other classes).  Enumerate algorithms and proofs in an
appropriate system (such as exponential function arithmetic) that the
algorithms do not return a wrong answer.  Run proved algorithms until an
answer is given.  Over the best provable algorithms, this algorithm has
at most an enormous constant factor overhead.  The question is whether
it runs in linear time.  On the other hand, if P<NP, a candidate hard
case (in coNP) for the algorithm is consistency of the system with
respect to proofs shorter than the input.

Dmytro Taranovsky
http://web.mit.edu/dmytro/www/main.htm