On Hardness and Lower Bounds in Complexity Theory (Thesis)
Report ID: TR-644-02Author: Viglas, Anastasios
Date: 2002-01-00
Pages: 100
Download Formats: |PDF| |Postscript|
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.