The Cerny Conjecture

The \v{C}ern'y conjecture (\v{C}ern'y, 1964) states that each n-state \san
possess a \sw\ of length $(n-1{)}^2$. From the other side the best upper bound for the \rl\ of n-state \sa\ known so far is equal to $\frac{n^3-n}{6}$ (Pin, 1983) and so is cubic (a slightly better though still cubic upper bound $\frac{n(7n^2+6n-16)}{48}$ has been claimed in Trahtman but the published proof of this result contains an unclear place) in $n$. In the paper the \v{C}ern'y conjecture is reduced to a simpler conjecture. In particular, we prove \v{C}ern'y conjecture for one-cluster automata and quadratic upper bounds for automata closed to one-cluster automata. Our approach utilize theory of Markov chains and one simple fact from linear programming.