Skip to Main Content
Theory of Computational Complexity, 2nd Edition
book

Theory of Computational Complexity, 2nd Edition

by Ding-Zhu Du, Ker-I Ko
June 2014
Intermediate to advanced content levelIntermediate to advanced
512 pages
17h 55m
English
Wiley
Content preview from Theory of Computational Complexity, 2nd Edition

Corollary 9.27

Proof

9.4 c09-math-1067 and the Polynomial-Time Hierarchy

In this section, we prove that c09-math-1068. From Theorem 9.26, we only need to show that c09-math-1069. The main idea is that the number of accepting computations of an NTM can be amplified without changing its parity. Recall that c09-math-1070 denotes the ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Theory of Computation

Theory of Computation

George Tourlakis

Publisher Resources

ISBN: 9781118594971Purchase book