Studies in Computational Complexity

这个项目集中在计算复杂性理论中的三个问题领域。第一部分旨在表明，在工作空间有限的计算环境中，随机性的使用不会显著增加计算能力，目的是增加我们对随机性作为计算工具的作用的全面了解。第二部分旨在确定小型布尔电路的计算限制，目的是更好地理解需要更多计算资源的计算问题的各个方面。最后一部分旨在改进最著名的基本图着色问题的精确解的算法，更大的目标是开发更广泛地适用于加速更广泛类别的困难计算问题的工具。

This project focuses on three problem areas in the theory of computational complexity. The first part aims at showing that in the context of computations which operate in limited work space, the use of randomness does not significantly increase computational power, with the goal of increasing our overall knowledge about the role of randomness as a tool in computation. The second part aims at ascertaining the computational limitations of small boolean circuits, with the goal of better understanding the aspects of computational problems that require more computational resources. The last part aims at improving the best known algorithms for exact solution of the fundamental graph coloring problem, with the larger goal of developing tools that may be more broadly applicable to speeding up wider classes of hard computational problems.***