On Hardness and Lower Bounds in Complexity Theory (Thesis)

Abstract:

In this work we are going to discuss and present lower bounds for
specific problems in restricted computation models, and show
connections between hardness and several problems in Computational
Complexity theory. In particular we are going to present the
following four results:

First, we consider the well known problem of Satisfiability. Proving
a hardness result for this problem is a famous long standing open
question, yet we have seen very little progress towards such a
result, even for restricted computation models. We prove a non-linear
time lower bound for solving satisfiability when restricted to use
only a small amount of space (time-space trade-off for
satisfiability). This was the first non-linear time bound for
Satisfiability in this model.

We also describe an interesting connection between the hardness of an
explicit problem and complexity class separations. The problem we
consider is that of deciding whether the intersection of a collection
of finite state automata is empty: either this problem requires large
circuits, or NL is not equal to NP. For the uniform case, either this
problem does not have fast algorithms or NL is not equal to P. On the
other hand if this problem is easy, the we can design improved
algorithms for subset sum and integer factoring, and we can also
prove that non-deterministic time has fast deterministic
simulations. These results point to a new way of separating
fundamental complexity classes (NL from NP, or NL from P) and raise
many interesting questions.

Considering the connection of the class P and the non-uniform class
of small depth and polynomial size circuits leads to some interesting
results. If every polynomial time computation can be done by a
non-uniform circuit of polynomial size and sub-linear depth (for
example if P is in non-uniform NC), then deterministic time can be
simulated in small space. This simulation would improve the well
known bound of Hopcroft Paul and Valiant.

A different approach to separating complexity classes is based on a
connection between computational complexity and the length of proofs
in propositional logic. We consider the correspondence between proof
systems and computation models. Starting from a class of automata,
we can define a corresponding proof system in a natural way. A new
proof system that can be defined through this correspondence is based
on the class of push-down automata. This system is strictly more
powerful than a certain variant of regular resolution and gives rise
to many interesting questions.