Studies on evaluation of difficulty of computational problem and verification of configurationality of computational effort class

NameIwamoto Chuzo
KeywordComputational effort class Turing machine Automaton Parallel computing machine model System evaluation
URLhttp://seeds.office.hiroshima-u.ac.jp/profile/en.516194d6735d4c02520e17560c007669.html

Research Summary

It is natural to think that the increased use of computing time and the amount of memory will result in more difficult problems being solved. However, it is known that it is very difficult to theoretically verify the configurationality of the difficulty of such problems. The problem of ''P≠NP,'' which is the famous outstanding problem in the field of computing machine science represents one example.
So far, our laboratory has verified various hierarchy theorems concerning the difficulty of problems by using the Turing machine which is the basic model of serial computing machine, PRAM which is a parallel computing machine model, and logic circuits. Further, we have theoretically clarified to what extent computing can be made faster by using the parallel computing method that is called alternation.

Appeal Point

Concerning problems in studies and development by enterprises and other organizations, we are ready to provide knowledge regarding their problems.


応用分野、想定業界・用途、企業への期待など
Study and development fields in which combination problems or large-scale computation is required


We are ready to provide knowledge to enterprises and other organizations which are interested in the above-stated fields.

Related Information

Created : 2008/04/01 18:06  Modified : 2011/07/28 9:55