Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
P and NP
View through CrossRef
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.
Title: P and NP
Description:
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.