Computability N Complexity Theory 2E – Steven Homer

Then, the following elegant and useful characterization of NP follows immediately from Theorem 6.1. Corollary 6.1. NP is the class of all languages A having a polynomial-time verifier. The proof follows by taking V to be the polynomial-time algorithm that accepts the relation R(x,y) in (6.2). Since the length of the witness y is a polynomial in the length of x, V runs in polynomial time in the length of x.

Example 6.1. Recall (Example 3.1) that the Hamiltonian Circuit problem is the problem of determining whether a graph has a Hamiltonian circuit. It is easy to show that the Hamiltonian Circuit problem belongs to NP: A nondeterministic Turing machine in polynomial time can, given as input a graph G, guess a sequence of vertices, and then accept if and only if it verifies that the sequence is a Hamiltonian circuit.

It is just as easy to show that the Hamiltonian Circuit problem belongs to NP by using Corollary 6.1: A verifier V for this problem should, given as input a graph G and a path p in G, accept if p is a Hamiltonian circuit, and reject otherwise. 6.2 The Class P Before continuing with our detailed discussion of nondeterminism, since the question of whether P = NP drives so much of this development, let us say a few words about the class P. Recall that we identify P with the problems that are feasibly computable and that we do so based on the evidence supporting Church’s and Cobham’s theses.

The simple distinction that makes theory of computing crucial to computing practice, and independent of the current state of technology, is seen by comparing a typical polynomial running time with an exponential one on modest-size input strings: An algorithm whose running time is n3 on strings of length 100 takes one million (1003) steps. However, an algorithm whose running time is 2n would require 2100 steps, which is greater than the number of atoms in the universe.

Contrary to naive intuition, improvements in hardware technology make this difference more dramatic, not less. As hardware gets faster, computers can handle larger input instances of problems having polynomial-time algorithms, but the number of steps required for an exponential-time algorithm remains unfathomably large.

Springer New York Dordrecht Heidelberg London Library of Congress Control Number: 2011941200 © Springer Science+Business Media, LLC 201 All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York, NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed is forbidden.

The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights. Printed on acid-free paper Springer is part of Springer Science+Business Media (www.springer.com) 1 We dedicate this book to our wives, Michelle and Sharon Preface to the First Edition 2001 The theory of computing provides computer science with concepts, models, and formalisms for reasoning about both the resources needed to carry out computations and the efficiency of the computations that use these resources.

It provides tools to measure the difficulty of combinatorial problems both absolutely and in comparison with other problems. Courses in this subject help students gain analytic skills and enable them to recognize the limits of computation. For these reasons, a course in the theory of computing is usually required in the graduate computer science curriculum. The harder question to address is which topics such a course should cover. We believe that students should learn the fundamental models of computation, the limitations of computation, and the distinctions between feasible and intractable.

In particular, the phenomena of NP-completeness and NP-hardness have pervaded much of science and transformed computer science. One option is to survey a large number of theoretical subjects, typically focusing on automata and formal languages. However, these subjects are less important to theoretical computer science, and to computer science as a whole, now than in the past. Many students have taken such a course as part of their undergraduate education. We chose not to take that route because computability and complexity theory are the subjects that we feel deeply about and that we believe are important for students to learn.

Furthermore, a graduate course should be scholarly. It is better to treat important topics thoroughly than to survey the field. This textbook is intended for use in an introductory graduate course in theoretical computer science. It contains material that should be core knowledge in the theory of computation for all graduate students in computer science. It is self-contained and is best suited for a one-semester course. Most of the text can be covered in one semester by moving expeditiously through the core material of Chaps.

This is a short excerpt from the opening of “” by Unknown, quoted for review and introduction purposes. All rights belong to the copyright holders.

Book Information

• Unique ID: 0393a741e0dbe629
• File Extension: .pdf
• File Size: 1,773,697 bytes (1.692 MB)
• Title: –
• Author: Unknown
• ISBN: 9781461406815, 9781461406822
• Pages: 316
• Language: English (en)

Reading & Word Statistics

• Estimated Reading Time: 578.9 minutes
• Total Words: 115,781
• Total Characters: 650,405
• Average Words per Page: 366.4
• Average Characters per Page: 2058.24

Most Frequent Words

turing (689), machine (577), let (566), input (548), theorem (543), proof (482), set (454), polynomial (421), time (398), every (334), function (307), complexity (275), accepts (275), tape (270), number (269), one (265), thus (262), computation (244), define (239), length (235), homework (231), following (231), show (230), problem (223), word (205), problems (192), space (191), corollary (183), accepting (181), computable (179), prove (179), machines (176), definition (172), follows (171), configuration (167), given (159), nondeterministic (158), classes (153), sets (153), since (153), theory (150), state (150), oracle (148), now (145), whether (145), class (142), language (134), steps (132), two (130), partial (127), first (125), belongs (124), value (124), decidable (124), sat (123), example (120), deterministic (120), string (118), circuits (117), size (117), functions (115), pspace (114), use (113), next (111), circuit (110), order (109), algorithm (109), formula (108), suppose (107), finite (106), log (106), result (104), assume (104), complete (102), procedure (101), symbol (100), boolean (97), lemma (97), defined (95), graph (94), case (93), hierarchy (92), contains (91), np-complete (91), observe (91), important (89), need (88), however (87), results (87), prover (87), languages (85), using (85), simulation (85), bpp (85), verifier (85), form (82), vertex (82), total (81), moves (79), halts (78).

PDF Download