Loading... Please wait...

Feasible Computations and Provable Complexity Properties

Hover over image to zoom

$81.50
Order Code:
CB30

 Product Description

by Juris Hartmanis

-

1978 / vii + 62 pages / Softcover / ISBN: 978-0-898710-27-4 / List Price $81.50 / SIAM/CBMS Member Price $57.05 / Order Code CB30

An overview of current developments in research on feasible computations; and a consideration of this area of research in relation to provable properties of complexity of computations.

The author begins by defining and discussing efficient reductions between problems and considers the families and corresponding complete languages of NL, DCSL, CSL, P, NP, PTAPE, EXPTIME, and EXPTAPE. Definitions and results are uniformly extended to computationally simpler natural families of languages such as NL, P, and CSL by using Log n-tape bounded reductions.

The problem of determining what can and cannot be formally proven about running times of algorithms is discussed and related to the problem of establishing sharp time bounds for one-tape Turing machine computations, and the inability to formally prove running times for algorithms is then related to the presence of gaps in the hierarchy of complexity classes.

The concluding discussion is on the possibility that the famous P=NP? problem is independent of the axioms of formal mathematical systems such as set theory.

Contents
Reductions and Complete Sets; L-Isomorphisms of Complete Sets; Structure of Complete Sets; Long Proofs of Trivial Theorems; What Can and Cannot Be Proven About Computational Complexity; Relativized P NP Problem.


ISBN: 9780898710274

 Find Similar Products by Category

 Product Reviews

This product hasn't received any reviews yet. Be the first to review this product!

 

newsletter

Follow us on

Copyright 2014 SIAM Bookstore. All Rights Reserved.
Sitemap | BigCommerce Premium Themes by PSDCenter

Society for Industrial and Applied Mathematics 3600 Market St., 6th Fl. Philadelphia, PA 19104-2688 USA +1-215-382-9800 FAX: +1-215-386-7999 www.siam.org email: siambooks@siam.org

Click the button below to add the Feasible Computations and Provable Complexity Properties to your wish list.