The 43rd Installment
“Practicability of Studies”

by Shogo Shimizu,
Assistant Professor, Master's Program of Information Systems Architecture

Practicability of studies

In my studies, I often take approaches that indicate the complexity of computational problems. In those studies, the concept of difficulty is important because it indicates that the targeted problem can be solved by computational class C and at the same time cannot be solved by computations below class C. C-class difficulty means that it has been theoretically proved that there is no algorism that can solve the problem more efficiently than C no matter how hard we try. In the modern computational model, problems belonging to a class higher than that which requires nondeterministic polynomial algorithms called NP-complete cannot be solved in a realistic amount of time. Unfortunately, it indicates that a little more complex problem in the real world (for example, a problem whose best solution cannot be obtained unless all the combinations of inputs are considered) cannot be solved within a realistic amount of time. For example, when a logical expression composed of logical variables is given, the problem of determining whether the assignment of variables by which the expression is true exists or not cannot be solved within a realistic amount of time if the size of the expression is large. In addition, there are problems that cannot be inherently solved by a computer, like one that asks for a determination of whether the computation stops or not for a given algorism and input. (A discussion on the inability to decide in this problem is similar to G?del's incompleteness theorems.)

By the way, when I make a presentation on those study results, though my explanation might be poor, I am almost always asked about efficiency in terms of practicability. For the major results of my studies sound negative because they indicate that a certain problem cannot be solved within a realistic amount of time. Of course, it might be possible to insist that I could prove the problem whose solvability was known to be solvable after all; thus, I presented the condition for solving it in polynomial time so that we would be able to solve the problem more efficiently. However, compared to studies in which a statement like "a new service was achieved" or "x % speedup in comparison to traditional methods was achieved" is presented, it is indeed hard to explain my studies in terms of practicability. (The exceptional field in which the concept of difficulty is immediately useful is about a problem like a code whose efficiency in solution is not required.) And to make matters worse, the results proved through effort tend to coincide with intuition after all. (So my explanation is understood by the audience, but doesn't surprise them at all.)

However, when we seek a solution to a rather difficult new problem, the first thing we have to do is to indicate that it is hard to find the best solution using standard tactics. Without it, it is impossible to explain the reasons for the questions of why there is no other method but heuristic or other methods, or why the problem has to be limited in order to be solved efficiently. If the difficulty is proved theoretically, it is always possible to put an end to the effort to seek the best solution. Thus the conclusion of difficulty supports the significance of the next study for the development of realistic solutions rather than the significance of its own.

Though the said example of the studies on computational complexity is within the scope of my limited experience and thus may be trivial, I would like to boldly say that one-to-one correspondence in terms of interesting applicability does not always hold true between an individual study for which novelty is required as an accumulation of wisdom and the practicability of the results of the study. These days, in particular, some achievement in a short period of time is often required. Of course, I admit that prospect is necessary for any study; however, I think that if we fail to define the position of the study through a comprehensive perspective and only seek attractive but unimportant details because it is too sensitive for practicability, we would not be able to create something essential in terms of science and technology. As one of the teachers belonging to this graduate school for training advanced professionals, I would like to make efforts at education and study by seeking a good balance between studies and practicability in the information science and IT fields (though it is not so easy for me…).