The Cerny Conjecture
Time and place
1:15 PM on Thursday, November 17th, 2016; NAC 4/148
Prof. Benjamin Steinberg (CCNY Math Department)
Abstract
The Cerny conjecture arose in 1964 from the question of synchronizing finite state machines. To formulate the idea concretely imagine you are a prisoner in a dungeon. The dungeon has several rooms connected by one-way tunnels which are painted blue or red. Each room has a red tunnel and a blue tunnel leaving it. All the rooms have a yellow door. The yellow door leads to certain death in each room except one whose door leads to freedom.
The good news: you have a map of the dungeon.
The bad news: you have no idea which room you are in.
The so-so news: A prisoner warden has informed you that there is a fixed sequence of blue and red tunnels that leads you to the good room no matter where you start from. But which sequence and how many times do you have to travel the tunnels?
Cerny conjectured that if you have a finite state machine with n states that admits an input sequence which synchronizes the machine to a fixed state irregardless of the initial state then there is such an input sequence of length at most (n-1)^2. Cerny constructed examples requiring this long an input sequence. The best upper bound to date is cubic, dating from 1978. Finding a minimum length synchronizing sequence is known to be an NP-complete problem and hence difficult unless P=NP.
We'll talk some of the more than 100 partial results on this problem.
