Lance Fortnow
- Published in print:
- 2017
- Published Online:
- May 2018
- ISBN:
- 9780691175782
- eISBN:
- 9781400846610
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691175782.003.0004
- Subject:
- Computer Science, Programming Languages
This chapter looks at some of the hardest problems in NP. Most of the NP problems that people considered in the mid-1970s either turned out to be NP-complete or people found efficient algorithms ...
More
This chapter looks at some of the hardest problems in NP. Most of the NP problems that people considered in the mid-1970s either turned out to be NP-complete or people found efficient algorithms putting them in P. However, some NP problems refused to be so nicely and quickly characterized. Some would be settled years later, and others are still not known. These NP problems include the graph isomorphism, one of the few problems whose difficulty seems somewhat harder than P but not as hard as NP-complete problems like Hamiltonian paths and max-cut. Other NP problems include prime numbers and factoring, and linear programming. The linear programming problem has good algorithms in theory and practice—they just happen to be two very different algorithms.Less
This chapter looks at some of the hardest problems in NP. Most of the NP problems that people considered in the mid-1970s either turned out to be NP-complete or people found efficient algorithms putting them in P. However, some NP problems refused to be so nicely and quickly characterized. Some would be settled years later, and others are still not known. These NP problems include the graph isomorphism, one of the few problems whose difficulty seems somewhat harder than P but not as hard as NP-complete problems like Hamiltonian paths and max-cut. Other NP problems include prime numbers and factoring, and linear programming. The linear programming problem has good algorithms in theory and practice—they just happen to be two very different algorithms.
Lance Fortnow
- Published in print:
- 2017
- Published Online:
- May 2018
- ISBN:
- 9780691175782
- eISBN:
- 9781400846610
- Item type:
- chapter
- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691175782.003.0003
- Subject:
- Computer Science, Programming Languages
This chapter discusses P and NP through Frenemy, an imaginary world where every pair of people comprises either friends or enemies. Frenemy has about 20,000 inhabitants. Every individual seems ...
More
This chapter discusses P and NP through Frenemy, an imaginary world where every pair of people comprises either friends or enemies. Frenemy has about 20,000 inhabitants. Every individual seems normal, but put two in close vicinity and a strange thing happens. Either the two take an instant liking to each other, immediately becoming the best of friends, or they take one look at each other and immediately become the worst of enemies. By examining social networking data such as Facebook and Twitter, computer scientists at the Frenemy Institute of Technology have put together a nearly complete database showing which pairs of people are friends and which pairs of people are enemies. The chapter then shows what these researchers can and cannot do with this data. It also presents other NP problems from a few other scientific fields where there is no known efficient algorithms.Less
This chapter discusses P and NP through Frenemy, an imaginary world where every pair of people comprises either friends or enemies. Frenemy has about 20,000 inhabitants. Every individual seems normal, but put two in close vicinity and a strange thing happens. Either the two take an instant liking to each other, immediately becoming the best of friends, or they take one look at each other and immediately become the worst of enemies. By examining social networking data such as Facebook and Twitter, computer scientists at the Frenemy Institute of Technology have put together a nearly complete database showing which pairs of people are friends and which pairs of people are enemies. The chapter then shows what these researchers can and cannot do with this data. It also presents other NP problems from a few other scientific fields where there is no known efficient algorithms.
