In the proof of TQBF-complete, it says if the input size is i, then the TM for the input has at most 2^i numbers of configuration. Can someone explain why? The proof is from: http://zoo.cs.yale.edu/classes/cs468/fall12/TQBF-complete.pdf
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Where did you read that? What was the surrounding context? We're more likely to be able to answer questions about some proof if you can provide excerpts from the proof to give us the relevant context (so we don't have to guess what the reasoning in the proof might be). $\endgroup$– D.W. ♦Commented Mar 24, 2017 at 0:15
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
0
Let $s(n)$ be the space used by Turing machine, $\Sigma $ is a input alphabet, $Γ$ is tape alphabet ( $Σ ⊆ Γ$ ) and $Q$ is a finite set of states. Then maximum number of different configuration bounded by $|Q| \times| Γ|^{s(n)}\times s(n)$. You have $s(n)$ many places and in each place you have choices and then you can derive the expression very easily.
$\begingroup$
$\endgroup$
1
I don't know which proof you're referring to, but i'd expect it's because the input is assumed to be binary. I.E. a binary string of length 1 can have two values, 0 or 1. A binary string of length 2 can have 4 values, 00,01,10,11, and a binary string of length 3 can have 8 values, and so on.
-
$\begingroup$ Ah, I can't get the idea. I can't understand why the possible configurations of a TM is related to the length of the input. $\endgroup$ Commented Mar 23, 2017 at 22:54
$\begingroup$
$\endgroup$
That's not what the proof says. Nowhere does the proof claim there are only $2^i$ configurations, where $i$ is the length of the input. In particular, in the proof you link to, $i$ is not the length of the input.
Rather, the proof says that every configuration can be encoded as a bitstring of length $c \cdot s(n)$, and consequently there are at most $2^{c \cdot s(n)}$ possible configurations. Then it goes on to consider a value of $i$ that is $c \cdot s(n)$.
