Index
 
Operating Systems
Java
Programming Languages
Hardware
Microsoft Technologies
Computer Science
Formal Methods
MM & Game Dev.
Theory Computing
Compilers
Database
Hardware
DS & Algorithms
OS
Network
Database
Network
Software Engineering
XML and XSL
Internet
Web Programming
Web Technologies
Physics
Bio-Chemistry
Mathematics
Medical
Redbooks
Unlisted/Miscellaneous

Contact Us

Freebookzone.com | What's New | Missing Link | Feedback

CS -> Theory



Book Title : Introduction to Computational Complexity
eBook download format(s) : pdf ps 
Author(s) : Martin Tompa
Section : CS -> Theory
Book Review:

Book Description
These are the lecture notes from a graduate course on Computational Complexity taught at the University of Washington. This topic fits in the middle of three of the fundamental areas of the Theory of Computation, which can be summarized with respect to their approaches to computational problems as follows:

- Computability: Determine whether an algorithm exist that solves a given problem.

- Computational Complexity: For those problems that are computable, determine a coarse analysis of their time and space requirements. Such analyses may well ignore the differences between polynomials, and concentrate on the difference between polynomial and exponential behavior.

- Analysis of Algorithms: For those problems that can be solved in polynomial time, determine a more exact analysis of their time and space requirements.

This text adopts some approaches that will appear unconventional. For example, alternating Turing machines are introduced very early, and deterministic and nondeterministic Turing machines treated as special cases. This simplifies many proofs, such as that of Savitch's Theorem, the P-completeness of the circuit value problem, the NP-completeness of the satisfiability problem, and the PSPACE-completeness of the quantified Boolean formula problem.

Another unconventional approach is to use log space reducibility rather than polynomial time reducibility when reducibility is first introduced in Chapter 5, and to begin with NL-completeness rather than the more important NP-completeness. The reason for this decision is twofold. First, the generic reduction in proving the NL-completeness of the directed graph connectivity problem is much simpler than the generic reduction normally used to prove the NP-completeness of the satisfiability problem, and thus gives the student a good "warmup" for the more important completeness proofs to come. Second, the NP-completeness proof of the satisfiability problem given in Theorem 8.7 is greatly simplified by the machinery built up in Chapter 7 on P-complete problems.




add to del.icio.us                 Digg Freebookzone.com!

You may use anyone of the download options


eBook VersionLook @ Amazon
Front Cover

Missing Link?, Report It and try these 2 + 1 alternates...
  
     Find 


Tell a Friend!

Similar Book titles in CS -> Theory section:
Introduction to Computer Science I
Cellular Automata and Complexity
An Introduction to the Theory of Computation (Principles of Computer Science Series)
Introduction to Symbolic Computation
An Introduction to Multigrid Methods
Categories, Types And Structures - An Introduction to Category Theory for The Working Computer Scientist
Computational Semantics and Type Theory
Parallel Complexity Theory
Lecture Notes on Algorithm Analysis and Computational Complexity (4th Edition)
Computational Category Theory
A Short Introduction to Queueing Theory
An Introduction to Computing
A Gentle Introduction to Haskell
Computation Complexity
Introduction to Objective Caml


Similar Book titles in Other sections:

Section: Bio-Chemistry
Introduction to Glycolysis
Complexity in Biological Information Processing
Computational Molecular Biology: An Introduction


Section: CS -> Compilers and Languages
Semantics with Applications: A Formal Introduction
An Introduction to GCC
Introduction to Programming Languages
Data, Syntax and Semantics - An Introduction to Modelling Programming Languages
Introduction to Machine Learning
Show all..


Section: Data Structures and Algorithms
Introduction to Computer Graphics
Algorithms and Complexity
Introduction to Algorithms
Complexity of Algorithms
Computational Geometry: Methods and Applications
Show all..


Section: DB -> Datawarehousing
Data Mining - An Introduction Student Notes


Section: DB -> Others
Introduction to Databases for the Web
Introduction to Databases for Web Developers
Introduction to Sybase


Section: DB -> Postgre SQL
PostgreSQL: Introduction and Concepts
An Introduction to MySQL


Section: DB -> SQL
Introduction to SQL
A Gentle Introduction to SQL
Structured Query Language (SQL) : A Practical Introduction


Section: Device Drivers
Introduction to Writing Windows CE Display Drivers


Section: Logic Design and Architecture
An Introduction to VHDL
The Complexity of Boolean Functions


Section: Microprocessor
CAN (Controller Area Network): Introduction and Fundamentals
Introduction to Microcontrollers
Introduction to PLC controllers
Introduction to 8080/8085 Assembly Language Programming


Section: Peripherals
Introduction to PCI


Section: Advanced Java
Introduction to Computer Science Using Java


Section: Java Enterprise Edition
Enterprise Java Beans, an Introduction


Section: Java User Interface
Java 2D: An Introduction and Tutorial


Section: Java Language
Introduction to Programming Using Java
Introduction to Interactive Programming In Java
Introduction to Programming (in Java) - An Interdisciplinary Approach
Introduction to Neural Networks with Java


Section: Mathematics
An Introduction to Neural Networks
Introduction to Group Theory
A Computational Introduction to Number Theory and Algebra
Introduction to Matrix Algebra
The Not So Short Introduction to LATEX 2e
Show all..


Section: Miscellaneous
An introduction to Cryptography
Introduction to Sound Processing
E-Commerce: An Introduction
Introduction to Marketing Models
A Gentle Introduction to TeX, a Manual for Self-study
Show all..


Section: Microsoft C Sharp (C#)
A Programmer's Introduction to C# (Second Edition)
Programmer Introduction to C#


Section: Networking
Introduction to Data Communications
Introduction to Computer, Internet & Network Systems Security


Section: GNU/Linux OS
Introduction to Linux
Introduction to Socket Programming
An Introduction to Tkinter
The Easiest Linux Guide You'll Ever Read - an Introduction to Linux for Windows Users


Section: Embedded and RTOS
Introduction to Robotics: Mechanics and Control


Section: OS Theory
A Short Introduction to Operating Systems


Section: Unix OS
Introduction to Unix for Web Developers


Section: Assembly Language
Introduction to RISC Assembly Language Programming
Programmed Introduction to MIPS Assembly Language
Introduction to Reverse Engineering Software


Section: C Language
Introduction to C and C++ Programming
Introduction to C Programming


Section: C++ Language
An Introduction to C++ and Object Oriented Programming
An Introduction to C++ Programming
Compilers and Compiler Generators: an introduction with C++
Introduction to C++ Programming I
Introduction to Object-Oriented Programming Using C++
Show all..


Section: Other Programming
Common Lisp: A Gentle Introduction to Symbolic Computation
Ada Distilled: An Introduction to Ada Programming
An Introduction to Programming in Emacs Lisp
An Introduction to Logic Programming Through Prolog
Job Control Language (JCL) Introduction
Show all..


Section: Scripting
An Introduction to Scheme and its Implementation
Introduction to TCL/TK
Concrete Abstractions: An Introduction to Computer Science Using Scheme
An Introduction to Python


Section: Smalltalk
Smalltalk: An Introduction to Application Development Using VisualWorks
Smalltalk and Object Orientation: An Introduction


Section: Redbooks Draft
IBM/Cisco Multiprotocol Routing: An Introduction and Implementation
GDPS Family - An Introduction to Concepts and Capabilities
IBM System Storage DS3000: Introduction and Implementation Guide
IBM System z9 Business Class Technical Introduction
Introduction to Workload Partition Management in IBM AIX Version 6
Show all..


Section: Redbooks
IBM TotalStorage: Introduction to SAN Routing
IBM System z9 Business Class Technical Introduction
Introduction to the New Mainframe: z/OS Basics
AIX V6 Advanced Security Features Introduction and Configuration
SAN Multiprotocol Routing: An Introduction and Implementation
Show all..


Section: Redpapers
IBM System p5 510 and 510Q Technical Overview and Introduction
IBM BladeCenter JS21 Technical Overview and Introduction
IBM System p5 185 Technical Overview and Introduction
IBM System p5 560Q Technical Overview and Introduction
IBM IntelliStation POWER 185 Technical Overview and Introduction
Show all..


Section: Redpapers Draft
IBM System p5 505 and 505Q Technical Overview and Introduction
IBM System p5 550 and 550Q Technical Overview and Introduction
IBM System p5 510 and 510Q Technical Overview and Introduction
IBM System p5 590 and 595 Technical Overview and Introduction
System x3755 Technical Introduction
Show all..


Section: Software Engineering
How to Design Programs: An Introduction to Programming and Computing
Task-Centered User Interface Design - A Practical Introduction


Section: Web Programming
Voodoo's Introduction to JavaScript
Introduction to Databases for the Web
A Programmer's Introduction to PHP 4.0


Section: Web Technology
Introduction to Dynamic HTML
Introduction to Adobe Photoshop
Introduction to Web Design
Introduction to HTML
Introduction to Web Design
Show all..


Section: XML, XSL & UML
A Gentle Introduction to XML
Introduction to XML for Web Developers
A Technical Introduction to XML (N. Walsh)
Introduction to XForms
Introduction to XML Programming
Show all..


Similar Books from Amazon :


Tell a Friend!


©2008 FreeBookZone.com - Home - Privacy Policy - Program Policy, Terms and Conditions