I'm writing a document about the infamous problem with theoretical computer science, P v.s. NP. But, first thing to take note, I am not a scientist and this is not a strictly formal document, however it is my own and all of the ideas are original,I have provided sources for any content that I have externally used.
An Introduction to theoretical computer science
In order for you to first understand what I’m talking about, you need to first understand the basics of computational complexity theory, which in its most basic form is the study of the mathematical functions that go into writing the algorithms that we use. The study of computational complexity however, also studies the efficiency of algorithms and what not. During the study of computational complexity theory, you should encounter tools such as the famous big Oh notation.
The Big Oh notation is used in computer science, you can think of it as a form of tool that we use to describe the performance and complexity of an algorithm. The Big Oh notation looks at the worst case scenario. We use the Big Oh notation to give us an idea on how well our algorithms work, this way, in theory, we can work out how many comparisons out algorithms make each time they’re run, we can also look at how many times an algorithm is run.
Now as we get further into computational complexity theory we can look at computational complexity classes. Now here we get to the likes of P and NP, both are different classes of complexity, meaning that they contain different types of problems, which will require different kinds of algorithms to solve them. An example of a problem which lies in the class of P is “what’s the answer of n*n?” provided that n is a reasonable number to compute in the modern day and age, such as 123213*123213. This would be a very quick problem to solve for any computer in the modern day and age, as we have enough processing power to compute and output the answer, it’s executed before we’re able to say snap.
Then we have problems which lay in other classes, such as the NP class, now the NP class consists of problems which are not so easy to compute, you can think of NP as ¬P (if not familiar with mathematical logic, think of it as ‘not’ P). The problems that lay within this class consist of more complicated problems, such as asking a computer what’s the best strategy to use to indefinite win this game of n*n chess? Now this is somewhat more complex than asking what’s the output from n*n, as the opponent player can make another move that could cause you, player one to end up in a losing position. Which is why you’d then need to find another strategy to regain your position in the winning position. This exact example includes a slight flavour of game theory, which is essentially the study of a problem which consists of many decisions, from many inputs/players.
NOTE: Game theory is incredibly applicable, to many things, you can apply game theory to politics, economics, biology, so on and so forth.
Anyhow, after a very brief and vague introduction to computational complexity theory, you can now begin to understand what my document is about. You don’t need to have a strong understanding of mathematics or scientific notation to understand the main body of my document, as I've approached this topic from a rather interesting angel.
Abstract
I will discuss how there may arrive real world implications if P vs. NP were to be proven that P=NP. I have discovered these potential problems by carrying out research and looking at different sources, stating the potential forms of the applications that could arrive upon the execution of P vs. NP, if proven P=NP. I will focus on the cure to cancer and the death of encryption, if P=NP is proven. I would like to go on to talk about the implications that could arrive if P≠NP were to be proven, however I fear that if I focus on both sides, I may exceed the word-count. I feel that I have come to a fair conclusion on how mathematics can affect the world, just by looking at P vs. NP.
Cure to cancer
A technology that could emerge from proving P=NP is the cure to cancer, so my sources believe, according to many different experts in the field. To support this statement, I will refer to source 1 which discusses how proving that P=NP could lead to the cure of cancer. Although a lot of people tend to think this would be an excellent application for humanity on a whole, and indeed it would, however, stereotypically speaking, people only tend to see this as a good thing. I feel that people tend to overlook the fact that this could prove to potentially be a bad thing, as well as a good thing.
Mortality Rates
If people were to stop dying of cancer, this would cause for population density to rise dramatically, according to source 2, “Each year globally, about 14 million people learn they have cancer, and 8 million people die from the disease”. Now if you were to apply this number of people to just 10 years, this is 80 million people, and you need to keep in mind that if all of these people were to survive cancer, then the population would increase even more again. Not only would we have people who have survived cancer, but let’s say that they then go on to have children, this would cause for a rapid increase in global population.
In the graphic below, you can see how cancer affects the population in the UK, only 50% of people who get cancer in England and Wales alone, survive cancer.
Population Density
When we take these numbers and look at the population density of the UK, this could be an actual issue alone, due to the small size of the UK and the population density, sooner or later people would run out of room to live. As you can see in the graphic below, the population density in England alone is 413 population per KM^2. You can see if you were to stop all cases of cancer leading to fatality, then you could see how population density in England would drastically increase. Only 50% of people manage to survive cancer at this moment in time. If you were to take these figures and then compare it to how many people within England go on to reproduce, you could then compare the figures to get a rough estimate as to how rapidly the population density would increase.
Now this could prove to be an issue as source 5 argues that you could fit only 10,000 million people using a 2-dimensional set up, within a single KM^2. Now this is the very limitation as to how many you could put in a KM^2, realistically speaking, people could not survive like this, as we need space for essential daily routines. In addition to land that would be needed to produce consumables, such as vegetables and fresh meats. Now a growth in population density increase could be an issue simply due to the fact that we could potentially run out of land/space.
Discussion
Looking at the other side of my argument, population density may not prove to be an issue upon the arrival to the cure to cancer. The mortality rate could stay roughly the same, expecting a dramatic decrease does not necessarily mean that would be the case. The mortality rate could be kept roughly the same by many other variables, such as other illnesses, cancer developing itself to become immune to the cure, etc. People could get into accidents, therefore even though I have some findings to support my theory, it isn’t necessarily accurate enough to be regarded as a fact, but more opinion orientated.
Source Analysis
Looking at my sources, I think I can fairly say that source1 seems fairly reliable simply as it’s a fairly academic video that seems to have a lot of good reviews and comments from many other users. I feel that source 2 is fairly reliable, simply because other sources that I have viewed have had similar statistics, in addition to the fact that this is a government based websites, hence the domain name of ‘.gov’. I can also say that I feel very comfortable in utilising source 3 as a reliable source, simply as the content comes from a well-established research group that carryout all kinds of world leading research. I also feel fairly reliant on the source 4 as this is another government based websites and it is fairly recent data that has been included. Finally for this section, source 5, I feel that this is also reliable, only because of the fact that it includes arguments to prove its findings. However, with this source it is debatable that the findings are not accurate as it may not account for people who are over average size, in addition to other potential variables of which may affect the findings of this source.
Death of Cryptography
Another implication that could arrive from proving P=NP is that it could or at least in theory, should destroy the likes of encryption, as NP problems like breaking encryption would take a lot less time to crack. Encryption could be cracked in P-time, according to source 6, looks at how this is a debatable matter and how this is a question that remains unanswered. However the likes of source 1 supports the theory that if proven P=NP, then “The encryption we use for online banking, would be easy to crack because they’re based on NP problems.”
Discussion
Now I feel that it is very possible that if P=NP then encryption and cryptography would have to drastically change in order to keep networking and online commerce safe. As source 1 points out, as encryption is currently based on NP problems, if P=NP, then this would lead to many problems such that carrying out any form of transaction or action online, that’s meant to remain private could potentially no longer be private. If the algorithm to allow NP problems to become P problems got released and it fell into the wrong hands, it could be used maliciously to attack many online businesses. For this section, I would’ve liked to have included more sources, and more details, but I feel that this may have required too much content, as the word count is limited.
Source Analysis
I feel that source 6 is partially reliable, however this source is nearly 20 years old and a lot of data and variables may have changed over this length of time, especially in a field of study that’s excelling and developing at an incredible rate. Now as this source is much more up-to-date and it has a lot of good reviews, I believe that this is a more reliable source, according to the date, even though this source doesn’t essentially include mathematical findings to support such a theory, it does have many good reviews, in addition to many views.
Conclusion
Even though I haven’t discussed how P≠NP, if P=NP I think I’ve supported the theory that mathematics can drastically change the world and how it works. Our understanding of mathematics and algorithms goes beyond the science that’s required, we need to understand more in-depth on how some simple mathematical formulas could change the world, and how much of an impact it would have.
I personally think that if P ≠NP, which most professionals believe is the case, I think that this would prove to also include issues for the future, such as the development of mathematics and the sciences. As a lot of the sciences are requiring complex problems to be solved, such problems that may fall into the computational class of NP. These developments are being halted by the power of computation, and if computers are unable to solve NP problems within P-time, then this proves that we have the issue of developing the sciences may require a substantial amount of time.
Sources
https://www.youtube.com/watch?v=YX40hbAHx3s
i. This source talks about how one application of P vs. NP could lead to the cure of cancer – 26 Aug 2014
ii. Accessed – 16 Nov 2015
iii. Source Type – Website Data Type – Videohttp://www.cdc.gov/cancer/dcpc/resources/features/worldcancerday/
i. “Each year globally, about 14 million people learn they have cancer, and 8 million people die from the disease. Research suggests that one-third of cancer deaths can be prevented, but sometimes services and technologies are not widely available, especially in low- and middle-income countries.” – 3 Feb 2015
ii. Accessed – 16 Nov 2015
iii. Source Type – Website Data Type – Statisticshttp://www.cancerresearchuk.org/health-professional/cancer-statistics
i. Statistics on cancer, including mortality figures. – 16 Nov 2015
ii. Graphic 1
i. Data Included – 2010 - 2012
i. “The latest data available for most cancers in the UK are: incidence 2011, mortality 2012 and survival 2010-11. Source years are specified in each section.”
iii. Accessed – 19 Nov 2015
iv. Source Type – Website Data Type – Statisticshttp://www.ons.gov.uk/ons/guide-method/compendiums/compendium-of-uk-statistics/population-and-migration/index.html
i. Graphic 3 – 01 July 2014
ii. Accessed – 19 Nov 2015
iii. Source Type – Website Data Type – Graphichttp://waitbutwhy.com/2015/03/7-3-billion-people-one-building.html
i. “A full square kilometer could fit 10 million people” – 05 Mar 2015
ii. Accessed – 19 Nov 2015
iii. Source Type – Website Data Type – Mathematical Argumentshttp://www.wisdom.weizmann.ac.il/mathusers/oded/PSX/npc-crypto.pdf
i. Academic paper talking about how it may or may not be safe to base cryptography on the assumption that P != NP – Feb1998
ii. Accessed – 29Nov 2015
iii. Source Type – Academic Paper Data Type – Proofshttp://www.laurentluce.com/posts/python-and-cryptography-with-pycrypto/
i. Graphic 4 – 22 April 2011
ii. Accessed – 29 Nov 2015
iii. Source Type – Article Data Type – Graphic