Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR15-029 | 18th February 2015 13:29

Inherent logic and complexity


Authors: Stanislav Zak
Publication: 2nd March 2015 09:34
Downloads: 1650


Abstract. The old intuitive question "what does the machine think" at
different stages of its computation is examined. Our paper is based on
the formal de nitions and results which are collected in the branching
program theory around the intuitive question "what does the program
know about the contents of the input bits" [1],[2],[3],[4],[5].
We further develop these results above and we present a formal counter-
part of the intuitive notion "what does the program think " at different
stages of its computation on the processed input word. The de nition is
constructed as the logical consequences of the de nition of the knowledge
about the contents of input bits above.
Our formal de nition is in a good relation to the world of intuitive ideas.
We prove the theorem saying that the programs which are allowed to
compute (think) in a more sophisticated way can compute more effec-
tively. We also demonstrate an example that for some programs a small
enrichment of their inherent logical possibilities implies a dramatic com-
plexity drop. So, our de nition lives up to the expectations inspired by
The present paper opens a large eld of possible investigations of rela-
tions between logic on one hand and complexity on the other hand.

ISSN 1433-8092 | Imprint