Identities of Perkins Monoid and Millennium Problem

Overview

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 (1)

• American Mathematical Society: Third Award of $500 $500

Competition history

• ISEF 2017 Mathematics · Entry MATH014

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.