3 ms·
It's an interesting question how much added flexibility decreases the time. If you add a letter to the pattern it increases the complexity by a factor of 36 (26
by bjterry 13y ago
It's an interesting question how much added flexibility decreases the time. If you add a letter to the pattern it increases the complexity by a factor of 36 (26 letters, 10 numbers), but if you add an optional letter it actually halves the complexity, because strings are acceptable either with or without the match. If their pattern was torbroke?ra?ge? then based on the time quoted, if it takes 2.5 years for 9 letters, we'd expect only 114 days for 9 letters plus three optional letters. The fact that they only have one letter missing means they probably didn't have much more than 2 optional characters, since you would expect on average half of them not to appear.