Friday, February 24, 2017

The Brachistochrone Problem

           This mathematical blog post will be focused on the Brachistochrone problem. This is a famous problem that dates back to the time of Newton, Leibniz and Bernoulli. Unlike many of the other problems mentioned in this blog, this one has been solved, regardless it is still a great mathematical problem. The first part of the post will cover the history of the problem. Then the second part will be an explanation of Bernoulli’s solution, and finally closing with a part on the geometrical representation of the problem.

            Brachistochrone comes from two Greek words, meaning, the shortest time. Johannes Bernoulli used this to describe a problem concerning traveling between two points with the effect of gravity. The problem can be imagined with two points, A, and B. These two points are on a plane, point A being slightly elevated above point B. The problem is, what would be the best past path for an object to roll down form point A to reach point B? This of course being which path would be the fastest path, hence the Greek term for shortest time. This is not as straight forward of a problem as it seems. There are two factors that come into play. The first being the distance traveled. A straight line has the shortest distance, so it would take an object less time. The second being the speed of the object. If there is a curve in the line, it allows for the object to accelerate, and therefore cover the longer distance faster. Galileo had purposed before Bernoulli that an arc of a circle would be the best path. The circle is better than the straight line, but it is still not the best solution to the problem. The balance lies in between a circle arc, and a straight line. Bernoulli came up with a solution to the problem, but rather than sharing the solution, he sent out the problem as a challenge to the other mathematicians at the time. These mathematicians included Leibniz, Newton, and Johannes Bernoulli’s brother Jacob. Bernoulli challenged them in order to show that he was the cleverest, or the smartest mathematician at the time. Some historians speculate that he was really only trying to rival his brother, but either way he was trying to show off his mathematical skills. It may have back fired on him though, because Newton solved it over night, when it took Bernoulli two weeks to solve it. Bernoulli, though not being able to solve it the fastest, came up with a rather clever way of looking at the problem.

            Bernoulli came up with a way of explaining the curve with light. Fermat at the time came up with a principle that light would move with different angles, through different mediums, to maximize the speed of the light. This can be proven with Snell’s Law. The important part of Snell’s law that needs to be understood with relation to this post is that light will take the best path when passing through different mediums. If light passes through multiple layers of a medium it starts to curve in line segments. If the number of mediums increases, the curve becomes smoother. If the number of mediums approaches infinite the curve for the best path of our object becomes apparent. This was Bernoulli’s solution, and it is correct.


            Johannes Bernoulli also saw some geometry in the curve. He recognized that at any point on the curve, the sin of the angle between the tangent line at that point, and the vertical line at the point, divided by the square root of the distance from the point, to the top of the start of the curve, is constant. He recognized that to be what is called a cycloid. A cycloid is the path of a rolling wheel along it radius. Imagine a wheel, and on the edge of the wheel an expo marker was taped so that it was flush with the radius and did not affect the roll of the wheel. If the wheel was rolled next to a white board a cycloid would be draw with the marker. However, the relation between the cycloid, and the discovery made by Bernoulli, is not as obvious as Bernoulli made it seem. At first the sin(theta)/sqrt(y) does not seem to have any relation to a rolling wheel. However, when looking at the wheel, and using some geometry it can be proven that the relation is directly proportional to the diameter of the wheel, this meaning since the diameter is constant the ratio of the sin(theta)/sqrt(y) is constant as well.

(cycloid)






Thursday, February 23, 2017

P vs. NP

In this blog post the focus will be on the P vs. NP problem. This problem is easy enough to explain in a post, but the real world applications of this problem are much too vast to be covered in a single post. So the main focus will be on the problem, and a few of its applications. First the problem, then how it relates solving Sudoku puzzles to curing cancer.

            The P vs. NP problem arose in the 1970’s. This is the time period when advances in computer technology were starting. At the time computer scientists realized that some problems were easier to compute then others. For example, a computer could do multiplication within a small amount of time, but could not compute the next perfect chess move in a timely manner. Computer scientists started grouping these problems as P and NP problems. Focusing first on P problems, P problems refers to problems that a program can solve in a reasonable amount of time, such as multiplication, or alphabetizing a given set entry of names. Then outside P problems, but still including P problems, is another category called NP problems. The NP problems are problems that take a long time to solve, but can be easily checked if given the solutions. A common example of this is a Sudoku puzzle. It takes a reasonable amount of time to solve a Sudoku, but it only takes seconds to check to see if the solution is valid. Now Sudoku puzzles have become easy to solve with the advancement of computers, but that does not change it to being a P problem. P stands for polynomial time, meaning the time in order to solve the problem, can written as a polynomial function. For example, going to back to multiplication, the bigger the numbers being multiplied get, the more time it takes to solve the problem. However, the time that it takes to solve then can be given as a polynomial function, like x^2 or x^3, meaning that the relation can be described using polynomials. NP refers to Non-deterministic polynomial time. This means that the amount of time it takes to solve a problem cannot be written as a polynomial function. Going back to the Sudoku problem, if the size of Sudoku board is scaled up the time taken to solve goes up exponentially and becomes difficult even for super computers. P problems are a sub category of NP problems, and over time computer scientists have found that some of the formerly thought NP problem were P problems. This is obviously not the case for all problem because then there would be no P vs. NP, but the idea that one day all NP problems will become P problems is a possible theory. This is a bit of controversy in computer science. Some computer scientists and mathematicians think that P will one day equal NP, meaning all NP problem will become P problems, and others think they will remain separate. This is the P vs. NP problem, can all NP problems become P problems, or will they remain as they are. The main problem with this problem, is the P vs. NP problem is an NP type problem in itself. That makes the problem tricky unless, it can actually become a P problem.

            There is another sub group, in fact there are many other grouping, but the focus is on the NP complete sub group. NP complete refers to root NP problems. In 1970’s computer scientists found that the NP problems were all the same kinds of problems with a little bit of variance. These root problems connect all the NP problems, and if they can be turned into P problems then all NP problems can change to P problems. In the 1970’s a grouping was released, but since then additions to the list include: Sudoku, Tetris, protein folding, and even crossword puzzles. Protein folding problems are apart our understanding of curing cancer, so it means that if there is a faster way found to simplify solving Sudoku puzzles, it could lead to the curing of cancer. This is why P vs. NP problem is such a big deal. This is why the P vs. NP problem is a Millennial prize problem. If it can be solved there is a possibility that the world around us could change immensely. There is also the possibility that it will not, if the NP and P problem remain separate. The point is no one knows, and it would be worth finding out.