In the Name of Allah Most Gracious, Most Merciful Simplicity vs. Complexity: The Theoretical Computer Science Perspective

摘要

The study of "what is simple?" and its reciprocal "what is complex?" is both fascinating and apparently very basic. Though, as this paper shall elaborate, the study is by no means as "simple" as its elementary nature may deceptively imply. Most of work done in physical sciences relate directly to the question of dissolving a system's complexity. The abstraction mechanism can be traced to have roots in the development of human languages or even in the origin of mathematical models. Computer science, comparatively an infant field, deals with complexity in the form of computational potential, level of abstractions, automated cognition, and adaptive software. The major part of this paper will review the prospective research areas within the realms of computer science for the quest of complex nature. The introductory part shall treat the topic historically highlighting the general concepts. The dream of total predictability of universe, the proved impossibility of this dream, and on the other hand successful applications of these same physical laws to everyday use add to the seriousness of the issue.