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, 2022. All Rights Reserved. An individual user may print out a PDF of a single chapter of a monograph in PRSO for personal use.date: 24 May 2022

Dealing with Hardness

Dealing with Hardness

(p.89) Chapter 6 Dealing with Hardness
The Golden Ticket

Lance Fortnow

Princeton University Press

This chapter demonstrates several approaches for dealing with hard problems. These approaches include brute force, heuristics, and approximation. Typically, no single technique will suffice to handle the difficult NP problems one needs to solve. For moderate-sized problems one can search over all possible solutions with the very fast computers available today. One can use algorithms that might not work for every problem but do work for many of the problems one cares about. Other algorithms may not find the best possible solution but still a solution that's good enough. Other times one just cannot get a solution for an NP-complete problem. One has to try to solve a different problem or just give up.

Keywords:   heuristics, approximation, NP problems, fast computers, algorithms, NP-complete problems

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.