On hardness and lower bounds in complexity theory.
详细信息
- 作者：Viglas ; Anastasios.
- 学历：Doctor
- 年：2001
- 导师：Lipton, Richard J.
- 毕业院校：Princeton University
- 专业：Computer Science.
- ISBN：0493457968
- CBH：3033052
- Country：USA
- 语种：English
- FileSize：3402496
- Pages：112
文摘
Proving hardness results (lower bounds) is a major problem in Theoretical Computer Science. Many practical problems and applications are based on hardness assumptions (for example, public key cryptography and security, pseudo-random generators, one-way functions, derandomization). Separating complexity classes is also a central question in Computational Complexity Theory that is closely connected with lower bounds.;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 t 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?NC/poly ), then DTIMEt ?SPACEt1-c for some constant c. This is a connection between the non-uniform depth of P and improving the known result for space simulations of deterministic time.;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.