P vs. NP problem

0:03Oh 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?

0:28Like 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

1:11NP 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

2:02if 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

2:45Mathematicians 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.