Mathoverflow at work

[griffon]

Сегодня удалось наблюдать замечательное. На Mathoverflow появилась красивая комбинаторика, начало доказательства которой предложил Питер Шор (да, тот которого алгоритм). Я честно пытался его доделать, но в это время красивую доделку предложил Сергей Иванов из ПОМИ.

Увы, на Mathoverflow по-прежнему мало Computer Science. Зато народ можно удивить

Comments

[yacoder]

А что такое NFA, DFA, ну и чем замечателен PSPACE??? =))

[griffon]

Это (не)детерминировнные конечные автоматы. С практической точки зрения PSPACE-полнота означает то, что на полиномиальный алгоритм лучше и не надеяться =) С теоретической --- много чем (например, есть свежий результат: QIP=PSPACE).