June 2014
Intermediate to advanced
512 pages
17h 55m
English
In this section, we prove that
. From Theorem 9.26, we only need to show that
. The main idea is that the number of accepting computations of an NTM can be amplified without changing its parity. Recall that
denotes the ...