• Complain

Lance Fortnow - The Golden Ticket: P, NP, and the Search for the Impossible

Here you can read online Lance Fortnow - The Golden Ticket: P, NP, and the Search for the Impossible full text of the book (entire story) in english for free. Download pdf and epub, get meaning, cover and reviews about this ebook. year: 2013, publisher: Princeton University Press, genre: Art. Description of the work, (preface) as well as reviews are available. Best literature library LitArk.com created for fans of good reading and offers a wide selection of genres:

Romance novel Science fiction Adventure Detective Science History Home and family Prose Art Politics Computer Non-fiction Religion Business Children Humor

Choose a favorite category and find really read worthwhile books. Enjoy immersion in the world of imagination, feel the emotions of the characters or learn something new for yourself, make an fascinating discovery.

Lance Fortnow The Golden Ticket: P, NP, and the Search for the Impossible
  • Book:
    The Golden Ticket: P, NP, and the Search for the Impossible
  • Author:
  • Publisher:
    Princeton University Press
  • Genre:
  • Year:
    2013
  • Rating:
    5 / 5
  • Favourites:
    Add to favourites
  • Your mark:
    • 100
    • 1
    • 2
    • 3
    • 4
    • 5

The Golden Ticket: P, NP, and the Search for the Impossible: summary, description and annotation

We offer to read an annotation, description, summary or preface (depends on what the author of the book "The Golden Ticket: P, NP, and the Search for the Impossible" wrote himself). If you haven't found the necessary information about the book — write in the comments, we will try to find it.

The P-NP problem is the most important open problem in computer science, if not all of mathematics. The Golden Ticket provides a nontechnical introduction to P-NP, its rich history, and its algorithmic implications for everything we do with computers and beyond. In this informative and entertaining book, Lance Fortnow traces how the problem arose during the Cold War on both sides of the Iron Curtain, and gives examples of the problem from a variety of disciplines, including economics, physics, and biology. He explores problems that capture the full difficulty of the P-NP dilemma, from discovering the shortest route through all the rides at Disney World to finding large groups of friends on Facebook. But difficulty also has its advantages. Hard problems allow us to safely conduct electronic commerce and maintain privacy in our online lives.The Golden Ticket explores what we truly can and cannot achieve computationally, describing the benefits and unexpected challenges of the P-NP problem.

Lance Fortnow: author's other books


Who wrote The Golden Ticket: P, NP, and the Search for the Impossible? Find out the surname, the name of the author of the book and a list of all author's works by series.

The Golden Ticket: P, NP, and the Search for the Impossible — read online for free the complete book (whole text) full work

Below is the text of the book, divided by pages. System saving the place of the last page read, allows you to conveniently read the book "The Golden Ticket: P, NP, and the Search for the Impossible" online for free, without having to search again every time where you left off. Put a bookmark, and you can go to the page where you finished reading at any time.

Light

Font size:

Reset

Interval:

Bookmark:

Make

THE GOLDEN TICKET

THE GOLDEN TICKET

P, NP, AND THE SEARCH FOR THE IMPOSSIBLE

LANCE FORTNOW

PRINCETON UNIVERSITY PRESS

PRINCETON AND OXFORD

Copyright 2013 by Princeton University Press

Published by Princeton University Press, 41 William Street, Princeton, New Jersey 08540

In the United Kingdom: Princeton University Press, 6 Oxford Street,

Woodstock, Oxfordshire OX20 1TW

press.princeton.edu

The epigraph for this book is taken from Charlie and the Chocolate Factory by Roald Dahl, copyright 1964, renewed 1992 by Roald Dahl Nominee Limited. Used by permission of Alfred A. Knopf, an imprint of Random House Childrens Books, a division of Random House, Inc. Any third party use of this material, outside of this publication, is prohibited. Interested parties must apply directly to Random House, Inc. for permission.

All Rights Reserved

Library of Congress Cataloging-in-Publication Data

Fortnow, Lance, 1963

The golden ticket : P, NP, and the search for the impossible / Lance Fortnow.

pages cm

Summary: The P-NP problem is the most important open problem in computer science, if not all of mathematics. The Golden Ticket provides a nontechnical introduction to P-NP, its rich history, and its algorithmic implications for everything we do with computers and beyond. In this informative and entertaining book, Lance Fortnow traces how the problem arose during the Cold War on both sides of the Iron Curtain, and gives examples of the problem from a variety of disciplines, including economics, physics, and biology. He explores problems that capture the full difficulty of the P-NP dilemma, from discovering the shortest route through all the rides at Disney World to finding large groups of friends on Facebook. But difficulty also has its advantages. Hard problems allow us to safely conduct electronic commerce and maintain privacy in our online lives. The Golden Ticket explores what we truly can and cannot achieve computationally, describing the benefits and unexpected challenges of the P-NP problemProvided by publisher.

Includes bibliographical references and index.

ISBN 978-0-691-15649-1 (hardback)

1. NP-complete problems. 2. Computer algorithms. I. Title.

QA267.7.F67 2013

511.352dc23

2012039523

British Library Cataloging-in-Publication Data is available

This book has been composed in Minion Pro

Printed on acid-free paper.

Printed in the United States of America

1 3 5 7 9 10 8 6 4 2

To Marcy, Annie, and Molly,

SO THAT THEY MAY KNOW WHAT I DO AND WHY I DO IT.

In England the famous scientist Professor Foulbody invented a machine which would tell you at once, without opening the wrapper of a candy bar, whether or not there was a Golden Ticket hidden underneath. The machine had a mechanical arm that shot out with tremendous force and grabbed hold of anything that had the slightest bit of gold inside it and, for a moment, it looked like the answer to everything.

Roald Dahl, Charlie and the Chocolate Factory

Picture 1ContentsPicture 2
Picture 3PrefacePicture 4

NEARLY HALF OF AMERICANS CARRY A SMARTPHONE, a computer more powerful than the supercomputers of just a couple of decades ago. Computers bring us the worlds information and help us sort through it. Computers allow us to communicate with almost anyone, anywhere. Computers can perform tremendous computations, from simulating cosmic events to scheduling complex airline routes. Computers can recognize our voices, our faces, our movements. Computers can learn our preferences and tell us what books, music, and movies we may like. In the not too distant future, computer technology will allow our cars to drive themselves. There seems to be no limit to what computers can do.

Or is there? This book explores the computational problems that we may never be able to compute easily. It does so through the most important challenge in computer science, if not all of mathematics and science, the oddly named P versus NP problem.

P versus NP is a mathematical challenge, one of seven recognized as a Millennium Prize Problem by the Clay Mathematics Institute, which puts a million-dollar bounty on its solution. But P versus NP means so much more.

P refers to the problems we can solve quickly using computers. NP refers to the problems to which we would like to find the best solution. If P = NP, then we can easily find the solution to every problem we would like to solve. If P = NP, then society as we know it would change dramatically, with immediate, amazing advances in medicine, science, and entertainment and the automation of nearly every human task.

If P NP, by contrast, then there are some problems we cannot hope to solve quickly. Thats not the end of the story, as we can create techniques that help us attack these problems in many cases. P NP means there is no automated way to solve some of the problems we want to solve. Still, knowing which tools dont work can help us figure out which ones do.

In August 2008, Moshe Vardi, editor-in-chief of the Communications of the ACM , asked me to write an article on the P versus NP problem. The Association for Computing Machinery is a major society serving computing researchers and professionals, and Communications is the societys main magazine devoted to articles of interest for that community.

At first I tried to push the article onto another computer scientist, but eventually relented. As Moshe put it to me, If physicists write popular articles (and books) about string theory, we should be able to explain what complexity theory has accomplished, Id hope. I wrote the article, aiming for the Communications audience, not just about the status of the P versus NP problem, which can be summarized as still open, but about how people deal with hard problems. The Status of the P versus NP Problem was published in the September 2009 issue and quickly became the most downloaded article in the Communications history.

The P versus NP problem remained a story to be told, and the popularity of the article suggested the time was right to tell this story, not just to scientists but to a much broader audience.

I used that short article as a framework for this book. Sections of the article become chapters here. I also took inspiration from Stephen Hawkings A Brief History of Time , which explains physics not through formulas and technicalities but with examples and stories. I attempt to do the same here to explore the spirit and importance of the P versus NP problem.

You will not find a formal definition of the P versus NP problem here; there are many great textbooks and websites that explore the definition of and technical results related to P versus NP. Reading this book will instead give you an appreciation of the possibilities and limits of computations as computers become such an integral part of our world.

Onward to P and NP!

Lance Fortnow
Evanston, Illinois

THE GOLDEN TICKET

Chapter 1

THE GOLDEN TICKET A CANDY MANUFACTURER DECIDES TO RUN A CONTEST and places a - photo 5

THE GOLDEN TICKET

A CANDY MANUFACTURER DECIDES TO RUN A CONTEST and places a handful of golden tickets inside its chocolate bars, hidden among the tens of millions of bars produced each year. The finders of these tickets will get a rare factory tour.

Next page
Light

Font size:

Reset

Interval:

Bookmark:

Make

Similar books «The Golden Ticket: P, NP, and the Search for the Impossible»

Look at similar books to The Golden Ticket: P, NP, and the Search for the Impossible. We have selected literature similar in name and meaning in the hope of providing readers with more options to find new, interesting, not yet read works.


Reviews about «The Golden Ticket: P, NP, and the Search for the Impossible»

Discussion, reviews of the book The Golden Ticket: P, NP, and the Search for the Impossible and just readers' own opinions. Leave your comments, write what you think about the work, its meaning or the main characters. Specify what exactly you liked and what you didn't like, and why you think so.