__
TR15-029 | 18th February 2015 13:29
__

#### Inherent logic and complexity

**Abstract:**
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 denitions 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 denition is

constructed as the logical consequences of the denition of the knowledge

about the contents of input bits above.

Our formal denition 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 denition lives up to the expectations inspired by

intuition.

The present paper opens a large eld of possible investigations of rela-

tions between logic on one hand and complexity on the other hand.