刊行物
｜ ENGLISH ｜
Jesper Jansson
My research is about algorithms. Informally, an algorithm is a method for solving a particular, well-defined computational problem. For example, in elementary school, we are taught an algorithm for multiplying two numbers. The amazing thing is that it doesn't matter which two numbers are given as input; the same method works for any pair of numbers. Also, on a basic level, it doesn't really matter if the method is carried out by a human or by an electronic computer, as long as whoever executes it follows all the steps exactly as specified. What is important, however, is that the process always ends up with the correct answer after a finite number of steps.
From a practical point of view, it's crucial to study algorithms because our information-intensive society has become so dependent on them. Modern inventions like the Internet, car navigation systems, the 1000 Genomes Project, Google's search engine, digital cameras, CT scanners, word processors, e-commerce, CAD systems, etc. wouldn't have been possible without good algorithms, and one may expect many technological advances in the near future to rely on them, too. So, what constitutes a "good" algorithm? Ideally, it should be efficient, in the sense that the total number of steps it requires should be small. In addition, I would say that a good algorithm should be conceptually simple and easy to implement on a computer. To formally prove its correctness or to analyze its efficiency or whatever might require some non-trivial mathematics and new theory, but once that part has been taken care of, it should be straightforward for a professional programmer to translate the algorithm into a computer program.
Brunch meeting with Dr. Sadakane (NII) and Dr. Sung (NUS) in January 2013 to discuss strategies for a new algorithm.
From a theoretical point of view, a compelling reason to study algorithms is to gain deeper insights into the nature of computation and information. (Sometimes, the existence of an algorithm is more interesting than the actual algorithm.) The currently known limits of computation may be due to our limited understanding of how things really work in the universe, or they may be inherent to the problems themselves. One fundamental question of Information Science is: What makes certain problems hard to solve and others easy? The field of Computational Complexity, developed since the 1960s, attempts to partially resolve the issue by classifying problems according to the amount of computational resources required to solve them, under different models of computation. Here, computational resources can mean time, memory, hardware (the number of logic gates or parallel processors), the number of random bits used by a randomized algorithm, etc. One key concept is "polynomial time". A problem that can be solved by an algorithm whose number of steps in the worst case is upper- bounded by some polynomial in the input size corresponds to our intuitive notion of "efficiently solvable". Fortunately for us, many important problems (e.g., multiplying two integers, mentioned above) are solvable in polynomial time. On the other hand, for certain other problems, it can be proved that no polynomial-time algorithms exist. Finally, for some problems such as factoring an input integer into prime numbers, it is unknown whether polynomial-time algorithms exist, even though widely used protocols for public-key cryptography like RSA are based on the somewhat risky assumption that they don't exist. (Curiously, in alternative models of computation such as the quantum computer model, integer factorization is solvable in polynomial time. Hence, if somebody could build a quantum computer in real life, the world's cryptographic communication systems would have to be redesigned immediately.)
To illustrate the fine borderline between the efficiently solvable and uncharted territory, consider the following scheduling problem: Given a number K and list of lectures along with the starting and ending times for each lecture, construct an assignment of a lecture hall to each lecture that uses at most K lecture halls, where lectures that overlap in time must be assigned to different lecture halls; if no such assignment of lecture halls exists, then output "Impossible.". (Technically, this is the NP-hard "Chromatic Number" problem in disguise.) It turns out that if K = 2 then there is a simple and fast method. However, for K = 3, the problem seems to suddenly become much, much harder! Obviously, we could enumerate all possible assignments and check each one if it is a valid solution or not, but such a naive algorithm would be very slow for large inputs since the number of possible assignments is exponential in the number of lectures. Actually, at this point in time, nobody knows if there exists a fast algorithm for the problem for any fixed K >= 3. This is quite remarkable. Incidentally, proving or disproving the existence of a polynomial-time algorithm for the problem for K = 3 would also settle the infamous "P vs. NP" question, selected by the Clay Mathematics Institute as one of its US $1,000,000 prize problems in the year 2000.
In my Hakubi research project, I want to combine the practical and theoretical aspects of algorithms research. I'm especially interested in combinatorial problems from the biological sciences that can be described elegantly using graphs and tree structures. Because of their expressive power and generality, graphs have been used for a long time in science and engineering, e.g., to show how objects such as the atoms of a molecule are connected or to specify various types of constraints such as precedence constraints in a complex manufacturing process. More recently, graphs have found novel applications in emerging research fields like social network analysis, the design of robust computer network topologies, frequency allocation in wireless networks, and bioinformatics (i.e., to represent metabolic pathways, protein-protein interactions, evolutionary relationships, or other kinds of structured biological information). In short, my goal is to design simple, efficient, and flexible algorithms for manipulating and comparing graphs that may be useful in many different practical situations, and to investigate the theoretical limitations of such methods.
（ジャンソン ジェスパー）
