Abstract Search

ISEF | Projects Database | Finalist Abstract

Back to Search Results | Print PDF

Identities of Perkins Monoid and Millennium Problem

Booth Id:



Finalist Names:
Mikhailovskii, Dmitrii (School: Instituto Federal de Educacao Ciencia e Tecnologia do Rio de Janeiro)

Millennium Problems are problems in mathematics that were stated by the Clay Mathematics Institute in 2000. One of these problems is related to the complexity of algorithms. The set of algorithms that solve a task in polynomial number of steps depending on the amount of input data are called polynomial and designated by P. The class of algorithms which are able to check in polynomial number of steps that an answer is indeed a solution for a problem is designated by NP. The Millennium Problem is so called "P versus NP problem". In 2005 there was proved the equivalence of this Problem and the feasibility of checking identities problem in Perkins monoid. Namely, if the problem of checking identities in Perkins monoid can be solved in polynomial time, then P is equal to NP. In the 1970s a group of mathematicians independently found a polynomial algorithm of checking identities in Brandt semigroup. It is still an open question for Perkins monoid (Brandt semigroup with identity element). In my project I search for such algorithm. The main result of the research is the proof of existence of the algorithm for identities of special type which I called cyclic identities. Cyclic identity is an identity u = v where heading and tailing letters of the words u and v are the same. This result is the step in finding a solution for problem of checking identities in Perkins monoid and P versus NP problem.

Awards Won:
American Mathematical Society: Third Award of $500