plakhov: (Default)
[personal profile] plakhov
Лесли Валиант получил Turing Award - самую почетную награду в области Computer Science. Ура!

Что сделал Валиант:
- создал PAC-learning framework
- показал (вместе с Вазирани), что NP полиномиально сводится к UNIQUE-SAT, а значит, и к PARITY-SAT; это стало первым шагом для доказательства теоремы Тода, а еще это источник некоторых несбыточных мечт для меня лично
- заметил, что умение считать перманент матрицы (почти то же, что детерминант, только все коэффициенты при слагаемых - плюс единицы) означает умение решать #P; это очень странно - интуитивно совершенно не ясно, почему эти две операции настолько отличаются по своей вычислительной сложности
- написал несколько отличных (к сожалению, боюсь, сильно недооцененных) работ о том, как некоторые вопросы теории эволюции или neuroscience (вот опять, как это по-русски? нейронауки?) оказываются на самом деле вопросами чистой вычислительной сложности, и как они решаются с этой точки зрения
- умудрился придумать noninteracting-fermion quantum circuits из чисто математических соображений, не понимая (по крайней мере, так утверждает Ааронсон), что он на самом деле придумывает

И наверняка еще кучу всего, о чем я не в курсе.

Date: 2011-03-10 08:55 am (UTC)
From: [identity profile] g-e-n-i-e.livejournal.com
А рыцарское звание ему подошло бы больше.

Date: 2011-03-10 10:08 am (UTC)
From: [identity profile] dmagin.livejournal.com
Про перманент интересно. То есть умение считать детерминант - это не то? Именно перманент эквивалентен задачам #P?

Date: 2011-03-10 10:27 am (UTC)
From: [identity profile] plakhov.livejournal.com
Да, конечно. Детерминант считается методом Гаусса за O(n^3), а перманент никто не умеет считать иначе, нежели за экспоненту от n. А класс #P даже сильнее, чем NP, так что умение считать перманент за полином было бы как минимум уберкибероружием, не говоря о прочем.

Примерно понятно, почему не существует аналогов метода Гаусса - в отличие от детерминанта, неизвестны простые "малые преобразования" матрицы, которые при этом сохраняли бы перманент.

Но в целом странно это, да. Например, в полях характеристики 2 детерминант и перменент вообще одно и то же, откуда же такие фундаментальные отличия в полях другой характеристики?

Date: 2011-03-10 03:09 pm (UTC)
From: [identity profile] http://openid.yandex.ru/worm-ii/ (from livejournal.com)
Дак вон в кольце полиномов теорема Ферма можно сказать, тривиальна, а в кольце целых чисел вон оно как получилось...

Date: 2011-03-10 07:08 pm (UTC)
From: [identity profile] plakhov.livejournal.com
Вы так это говорите, как будто понимаете, почему так получается. :)
Ну, в смысле, что именно делает великую теорему Ферма (или, там, collatz conjecture) внезапно такими сложными в Z. По-моему, чем обусловлена сложность доказательств, людям понятно еще меньше, чем тот же вопрос насчет вычислительной сложности.

Date: 2011-03-11 12:13 pm (UTC)
From: [identity profile] http://openid.yandex.ru/worm-ii/ (from livejournal.com)
Нет, не понимаю :)
Просто нет у меня такого ощущения, что алгебраическая структура должна всё определять. Обидно, конечно, что мы не можем решить сразу целую кучу задач, поднявшись уровнем абстракции выше, а должны копаться в этой куче вручную...
Но меня тоже впечатляет результат про перманент. Удивляет, что такие вещи вообще можно доказывать.

Date: 2011-03-10 03:10 pm (UTC)
From: [identity profile] itman.livejournal.com
Теория сложности - это крутая и интересная математика. Но есть два но:
ее мало, кто понимает и соответственно читает (это не алгоритмы какие-нибудь и не машинное обучение с NLP)
по всей видимости, это имеет не очень большой выхлоп в смысле практических решений.

Date: 2011-03-10 07:10 pm (UTC)
From: [identity profile] plakhov.livejournal.com
Ну это лотерея такая. Выигрыш маловероятен, но слишком уж гигантский, чтобы его игнорировать.

Date: 2011-03-10 06:58 pm (UTC)
From: [identity profile] vivkin.livejournal.com
Не знаю как neuroscience по-русски, а computer science это информатика :)

Date: 2011-03-10 07:03 pm (UTC)
From: [identity profile] plakhov.livejournal.com
ненавижу это слово

Date: 2011-03-10 07:10 pm (UTC)
From: [identity profile] vivkin.livejournal.com
Чем слово провинилось?

Date: 2011-03-10 07:10 pm (UTC)
From: [identity profile] plakhov.livejournal.com
присутствием в школьной программе, например

Date: 2011-03-10 07:19 pm (UTC)
From: [identity profile] vivkin.livejournal.com
А биология или химия никак не смущают?

Date: 2011-03-10 08:29 pm (UTC)
From: [identity profile] plakhov.livejournal.com
информатика - это не биология или химия, это как природоведение или ОБЖ

Date: 2011-03-10 09:07 pm (UTC)
From: [identity profile] vivkin.livejournal.com
Да-да а "Компьютерная наука" это как "Русский язык". Глупости. CS по-русски это информатика. Все эти школы, ОБЖ и прочее к предметной области не имеют никакого отношения

Date: 2011-03-11 08:02 am (UTC)
From: [identity profile] plakhov.livejournal.com
Химический факультет МГУ.
Я - химик,занимаюсь химией, наука такая.
Физический факультет МГУ.
Я - физик, занимаюсь физикой, наука такая.

Факультет информатики МГУ, я - информатик, занимаюсь неведомой Е.Х.

Ололо.

Date: 2011-03-10 07:12 pm (UTC)
From: [identity profile] 109.livejournal.com
информатика - это то, что преподаётся в средней школе на компьютерах Правецъ.

Date: 2011-03-12 10:05 am (UTC)
From: [identity profile] metaguest.livejournal.com
как некоторые вопросы теории эволюции или neuroscience (вот опять, как это по-русски? нейронауки?) оказываются на самом деле вопросами чистой вычислительной сложности, и как они решаются с этой точки зрения

Вы не подскажете, о каких статьях речь ?

Profile

plakhov: (Default)
plakhov

August 2017

S M T W T F S
  12345
6789101112
13141516171819
20212223242526
2728293031  

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 22nd, 2017 02:46 am
Powered by Dreamwidth Studios