# 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.