Minimum Weight Triangulation Problem
By Nicolau Andres Thio, The University of Melbourne
In my project I studied the minimum weight triangulation problem. This is an interesting problem to look at because as far as computer scientists know, an efficient algorithm to find a solution might not exist; it is part of a set of computational problems known as NP-Hard. That is what this blog post is about, a brief explanation of NP-Hardness: one of the millennium problems, the most important question in algorithmic computation, and an answer that will bring US $1,000,000 to the one that can answer it: does P = NP?
Let’s start with the basics of computer science. The concept of the complexity of an algorithm means how expensive it is to find the answer to a given problem with n objects. For example, finding the number of appearances of the number 2 in a set of n numbers will have complexity O(n), since we need to look at each number in the set once. Given n points on a plane, finding the closest point to each respective point will be O(n2), since from each point we need to look at all the other points. With this concept in mind we move on to labelling the complexities. If a problem can be solved with an algorithm of complexity of the form O(nc), where c is a constant, we call it polynomial time. This can be thought of as an efficient algorithm. On the other hand, other complexities such as exponential or factorial (O(cn) and O(n!) respectively) are not really efficient; even for moderately small values of n, a lot of operations need to be done to solve the problem. To picture this, if a problem has 100 objects, an O(n2) complexity algorithm will require 10,000 operations, whereas one with O(2n) complexity will take more than 1030 operations.
Now we can look at the question we want to answer. First of all, P stands for finding an answer in polynomial time, meaning quickly. If a problem lies within P, the answer can be found quickly; for instance, is there a 2 in this list of n numbers? takes O(n) to answer (look at each number once) and therefore lies in P. Secondly, NP stands for checking if an answer is valid; if a problem lies within NP, an answer can be checked quickly. For example, does this set of numbers have a subset which adds up to 0? An answer can be checked really quickly since the only thing to do is add the numbers of a given answer (a subset) and see if they are equal to 0. So, this problem lies within NP. The problem is that currently, an algorithm that finds such a subset in polynomial time does not exist (the current fastest takes 2n-n-1) (Horowitz & Sartaj, 1974).
So, the question that a lot of scientists want an answer to is: if a problem lies within NP, does it also lie within P? To prove a positive answer, a polynomial time algorithm needs to be found for any given NP-Hard problem (such as the minimum weight triangulation problem). A negative answer might be a bit trickier to prove. Either way however, if someone finds an answer that will make a lot of people happy. And she/he will become a millionaire.
Nicolau Andres Thio was one of the recipients of a 2016/17 AMSI Vacation Research Scholarship.