Leslie Valiant
Mar. 10th, 2011 11:09 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
plakhovЛесли Валиант получил Turing Award - самую почетную награду в области Computer Science. Ура!
Что сделал Валиант:
- создал PAC-learning framework
- показал (вместе с Вазирани), что NP полиномиально сводится к UNIQUE-SAT, а значит, и к PARITY-SAT; это стало первым шагом для доказательства теоремы Тода, а еще это источник некоторых несбыточных мечт для меня лично
- заметил, что умение считать перманент матрицы (почти то же, что детерминант, только все коэффициенты при слагаемых - плюс единицы) означает умение решать #P; это очень странно - интуитивно совершенно не ясно, почему эти две операции настолько отличаются по своей вычислительной сложности
- написал несколько отличных (к сожалению, боюсь, сильно недооцененных) работ о том, как некоторые вопросы теории эволюции или neuroscience (вот опять, как это по-русски? нейронауки?) оказываются на самом деле вопросами чистой вычислительной сложности, и как они решаются с этой точки зрения
- умудрился придумать noninteracting-fermion quantum circuits из чисто математических соображений, не понимая (по крайней мере, так утверждает Ааронсон), что он на самом деле придумывает
И наверняка еще кучу всего, о чем я не в курсе.
Что сделал Валиант:
- создал PAC-learning framework
- показал (вместе с Вазирани), что NP полиномиально сводится к UNIQUE-SAT, а значит, и к PARITY-SAT; это стало первым шагом для доказательства теоремы Тода, а еще это источник некоторых несбыточных мечт для меня лично
- заметил, что умение считать перманент матрицы (почти то же, что детерминант, только все коэффициенты при слагаемых - плюс единицы) означает умение решать #P; это очень странно - интуитивно совершенно не ясно, почему эти две операции настолько отличаются по своей вычислительной сложности
- написал несколько отличных (к сожалению, боюсь, сильно недооцененных) работ о том, как некоторые вопросы теории эволюции или neuroscience (вот опять, как это по-русски? нейронауки?) оказываются на самом деле вопросами чистой вычислительной сложности, и как они решаются с этой точки зрения
- умудрился придумать noninteracting-fermion quantum circuits из чисто математических соображений, не понимая (по крайней мере, так утверждает Ааронсон), что он на самом деле придумывает
И наверняка еще кучу всего, о чем я не в курсе.
