Jump to ContentJump to Main Navigation
The Golden TicketP, NP, and the Search for the Impossible$
Users without a subscription are not able to see the full content.

Lance Fortnow

Print publication date: 2017

Print ISBN-13: 9780691175782

Published to Princeton Scholarship Online: May 2018

DOI: 10.23943/princeton/9780691175782.001.0001

Show Summary Details
Page of

PRINTED FROM PRINCETON SCHOLARSHIP ONLINE (www.princeton.universitypressscholarship.com). (c) Copyright Princeton University Press, 2020. All Rights Reserved. An individual user may print out a PDF of a single chapter of a monograph in PRSO for personal use.date: 26 February 2020

Proving P ≠ NP

Proving P ≠ NP

Chapter:
(p.109) Chapter 7 Proving P ≠ NP
Source:
The Golden Ticket
Author(s):

Lance Fortnow

Publisher:
Princeton University Press
DOI:10.23943/princeton/9780691175782.003.0007

This chapter focuses on a few of the ideas that people have tried to solve the P versus NP problem. These have not panned out to anything close to a solution to the problem. To prove P ≠ NP one needs to show that no algorithm, even those that have not been discovered yet, can solve some NP problem. It is simply very difficult to show that something cannot be done. However, it is not a logically impossible task. The only known serious approach to the P versus NP problem today is due to Ketan Mulmuley from the University of Chicago. He has shown how solving some difficult problems in a mathematical field called algebraic geometry may lead to a proof that P ≠ NP. However, resolving these algebraic geometry problems will require mathematical techniques far beyond what is available today.

Keywords:   P versus NP problem, algorithms, NP problem, Ketan Mulmuley, algebraic geometry

Princeton Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.

Please, subscribe or login to access full text content.

If you think you should have access to this title, please contact your librarian.

To troubleshoot, please check our FAQs , and if you can't find the answer there, please contact us.