For a Boolean expression formula φ,
For a binary literal $i∈(0, 1)^l $
V(φ,i) is an Turing algorithm which decides whether i satisfies φ or not
if φ(i)=true then V(φ,i)=1
if φ(i)=false then V(φ,i)=0
I heard that the machine V works very efficiently.
My question is, how much efficient?
let m=digit of Boolean φ and let $l$=digit of i,
Time ( V(φ,i) ) ≤ O( $(m+ $l$)^3$) ? or
TIme ( V(φ,i) ) ≤ O( $(m+ $l$)^2$)?
The number of steps(quadratic or cubic) of a Turing machine is not so interesting, because it might use steps just for travelling on the tape. For instance if you allow two tape, you can have quadratic acceleration. It gives a better idea to evaluate the number of steps of an algorithm in a reasonable programming language. Here we can consider that it is linear, because it can remove boolean operators one after the others (starting with the innermost), and keeping track of the value.
For instance ((not (0 and (1 or 1))) or 0) will be reduced to ((not (0 and 1)) or 0), then ((not 0) or 0), then (1 or 0) and finally 1. You can even get shortcuts by using lazy evaluation : (1 or (...)) evaluates to 1 and same with 0 and 'and'.
So it is reasonable to say that this algorithm is in $O(m)$ (because $l\leq m$, otherwise no need to read the bits that do not appear in the formula).
