The Complexity Theory Companion
Edition: 1 edition
Publisher: Springer
Published: December 18, 2001
Language: eng
Format: Hardcover
Number of pages: 382
ISBN-13: 9783540674191
Subjects: Algorithms & procedures; Combinatorics & graph theory; Mathematical theory of computation; Probability & statistics; Computers - General Information; Algorithms (Computer Programming); Theory Of Computing; Computers; Computer Books: General; System Theory; General; Algorithms; Complexity Theory; Computers / Computer Science; Foundations; Theoretical Computer Science; Computational complexity; Computer Science; Programming - General
First sentence: Before we turn to Mahaneys Theorem-NP has sparse complete sets only if P = NP-and its generalization to bounded-truth-table reductions, we first prove two weaker results that display the self-reducibility-based tree-pruning approach in a simpler setting.