Main content
Course: Breakthrough Junior Challenge > Unit 2
Lesson 1: 2018 Challenge — MathematicsP vs. NP problem
By Ayesha Ahmed.
Creativity, ingenuity, luck. All concepts that set apart the most brilliant minds from the rest. But also concepts we cannot strictly define. After all, there are no set of rules for genius. Well, actually, there might be. This idea is exactly what the P vs. NP problem attempts to encapsulate: can we create a map of achieving "creativity"? Can abstract problems like "luck" be converted into easily computable problems like multiplication? Can we create a strict set of steps, an algorithm, to engineer luck and creativity? We just don't know. If not, it means there are certain problems we will never be able to solve. We will be doomed to ignorance on a large sense. But if yes, suddenly even problems previously thought to be too hard to solve become's easy enough for anyone to do. This completely redefines our values of brilliance because when everyone is a genius, no one is.
Creativity, ingenuity, luck. All concepts that set apart the most brilliant minds from the rest. But also concepts we cannot strictly define. After all, there are no set of rules for genius. Well, actually, there might be. This idea is exactly what the P vs. NP problem attempts to encapsulate: can we create a map of achieving "creativity"? Can abstract problems like "luck" be converted into easily computable problems like multiplication? Can we create a strict set of steps, an algorithm, to engineer luck and creativity? We just don't know. If not, it means there are certain problems we will never be able to solve. We will be doomed to ignorance on a large sense. But if yes, suddenly even problems previously thought to be too hard to solve become's easy enough for anyone to do. This completely redefines our values of brilliance because when everyone is a genius, no one is.
Want to join the conversation?
So from what I understand is that p=np is getting into probability mathematics, which seems to be the nature of what exactly quantum is. In my eyes quantum theory is more simply put probability theory as this needs to be defined as a single quantity (which might be what the entangling process is, or, the hypothetical string that holds together the two quanta), but that is besides the point.
So here's a thought experiment for you: Let's define luck, or what it means to be lucky. In order for luck to be involved, there needs to be a game played. So, for example, let’s say there is a game with a 1% win probability and a 99% loss probability, with only one chance to play the game. The game is played and results in a win. That was rather lucky, right? Well, no. Where was luck actually involved here? Nobody won the game. The game just played itself and had an outcome. There needs to be a player playing the game (think observer to reality as applied to quantum theory).
So let’s say we now have a player playing the same game with the same win/loss probabilities as before with the stipulation the player only gets 1 attempt. Let’s say the player plays the game and get a winning outcome the first time. That was rather lucky of the player. Luck being defined as winning with limited attempts despite the probabilities.
But now let’s say the player plays the same game with the same win/loss probabilities as before 100 times. There are three possible scenarios for the player concerning luck which I will explain. First, let’s say the player wins 2 times and loses 98 times. The player got lucky, because the expected result would be 1 win, 99 losses. Now then, let’s say the player gets 0 wins and 100 losses. Well that is rather unlucky because the player should expect to win at least once in the 100 attempts. So what about this third option here? The player wins 1, and losses 99 times. This is the expected result, and luck was never a factor to begin with. But wait, how does the expected result pertain to luck? The person was neither lucky/unlucky so luck does not apply. That means there is something that isn’t luck.
Luck only applies to games, and if everything is a game, then luck exists. Is life a game? I don’t know the answer to that. My hunch is to say everything is games. So does that mean everything boils down to luck? Games need players to play, and people get better at games of skill the more they play them. So are any games games of skill? People seem to get better as they do something, and develop skill, but some who work equally hard develop more skill than others because they had different starting positions. That’s still lucky of them. Or is it all just luck, and skill some construct of luck? Even so, how does this apply to emotions, art, and creativity?
This question I think is answerable, and the answer you’re looking for is, p =/= np because things of the same category that are different are not the same. Or in other words, things that are different, are different. AS those things that are different that are different are different, ad infinitum. Or in otherwords, differences exist. That means that the what everything boils down to is differences. Or in otherwords, difference.
But what makes things different?(7 votes)
Video transcript
Oh Hi. I was just trying to create an algorithm to solve Sudoku puzzles but it's not working out too well. What's an algorithm? So an algorithm is kind of like a cooking recipe a series of steps we follow in order to achieve a particular goal We've created efficient algorithms as solutions to so many problems But what I really want to know is is there a way to create an algorithm for something more abstract? Like luck? That question is the core of the P versus NP problem So firstly computer scientists try to group problems based on how difficult they are to solve The easy problems are categorized into the P class. These are problems that are easily solvable and whose answers are easily recognized like multiplication Computers can easily multiply two very big numbers in seconds Even if the numbers being multiplied grow exponentially the solving time does not in fact P stands for polynomial time meaning the solving time increases as a polynomial function of the problem To check an answer you just compare it to the correct solution Some harder problems are i n NP they're hard to solve but their answers are easily checked NP stands for non deterministic polynomial time Np-complete or NPC problems are the hardest problems in this class Non-determinism just means you can't find an answer without trial and error. like in this Sudoku grid. What's the number here? You need to try many before knowing the answer Solving problems through this way of guessing works when the problem is small But as it gets larger the options you need to try grow exponentially and to get every answer right on the first go you'd need to somehow be extremely lucky or engineer luck Checking a solved Sudoku grid is easy See if every column and row contain exactly one instant of the numbers 1 to 9 This sums up the P versus NP problem, can we somehow convert difficult NP problems into P problems we can solve efficiently if yes, how would we even do that? let me explain with an analogy a person that can solve a math problem at certain difficulty can solve any problem below that difficulty similarly, if an algorithm can efficiently solve an NPC problem every NP problem below it in terms of complexity can be solved efficiently by a similar algorithm pushing NP into P We just don't know if such an algorithm exists or not The Clay Institute of Mathematics will award you with a million dollars if you do have a definite answer though So what are the implications if P is equal to NP well, we suddenly get answers to problems we've considered too difficult to solve overnight Protein folding becomes easier to understand helping us cure cancer Mathematicians and scientists become redundant because making breakthroughs is no longer a function of luck or creativity But following an algorithm that anyone could do Is that a good or bad thing? You decide.