о сложности, несколько ссылок

[avva]

(эта запись может быть интересна людям, интересующимся математикой и информатикой)

1. Забавная пародия на многочисленные доказательства P?=NP (их, конечно, меньше создают, чем доказательств теоремы Ферма, но тоже хватает).

2. На днях прочитал обзорную статью, которую несомненно рекомендую всем математикам (и близлежащим), кто хочет получить представление о современной теории сложности (complexity theory):

Avi Widgerson, P, NP and Mathematics - a computational complexity perspective (PDF)

Очень хорошее изложение как начал, так и сути главных результатов последних 20 лет примерно (скажем, circuit complexity, the PCP theorem, proof systems итд.)

Если я смогу найти для этого время, мне бы хотелось разобраться во многом из того, о чем рассказывается в этой статье: в частности, в Natural Proofs и в док-ве PCP theorem.

Comments

Уважаемый Anatoly Vorobey,

[(Anonymous)]

я не математик, и не знаю, что в математике понимают под "сложностью", но мне возможно предстоит однажды (не знаю когда) решать вот какую проблему. Представьте себе, две программы, способные обучаться, играют в некую игру друг против друга. Программы разные, соответственно одна обучается лучше и выигрывает, другая проигрывает. Так вот, может быть ситуация, когда программа хорошо обучается простым (в обыденном смысле) играм и плохо сложным, или наоборот. Хотелось бы иметь какой-то обоснованный способ относительной оценки сложности игры, чтобы можно было сказать, вот эта игра в два раза сложнее той игры, потому-то. Допустим для простоты, что игры будут отличаться только в одном каком-то параметре. Можете ли Вы мне что-нибудь сказать на эту тему? Только так чтобы я понял, повторюсь, я в математике полный ноль.

Re: Уважаемый Anatoly Vorobey,

[avva.livejournal.com]

К сожалению, вопрос слишком туманно задан, на него трудно что-то определенное ответить. О какого рода "играх" идет речь? есть ли между ними что-то общее? можно ли построить модель общей игры, так что те правила игр, которым должны научиться машины, являются частным случаем общей простой модели?

У математиков есть несколько понятий сложности, но ни одно из них не подходит к "играм вообще". Достаточно общее понятие игр изучают в теории игр, но там редко говорят о проблеме обучения машин играть в игру, т.е. вести себя в ней несовершенно, но все лучше и лучше - специалистов в теории игр больше интересуют вопросы существования выигрышного алгоритма вообще, например. С другой стороны, есть область machine learning, где именно изучают, как программы могут обучаться какой-то информации о какой-то проблеме. Я мало знаю об этой теме, но мне кажется, что у них тоже нет готовых рецептов для "игр вообще". Может, если сформулировать конкретную модель игры с параметрами в правилах, о которой идет речь, ее можно будет представить как задачу из области machine learning и что-то нетривиальное об этом сказать. Но это только догадка, на самом деле я совсем почти не знаю эту область.

Спасибо, уточнение.

[(Anonymous)]

Меня конечно интересует не игра, а игроки, программы. Игру предполагается использовать только для их оценки. Какую именно - это, в частности, я хотел бы понять из Вашего ответа. Хотя бы какого типа. На что похоже. Какими качествами должна обладать игра. Надо, чтобы её сложность можно было изменять, меняя один или несколько параметров. Если есть несколько видов "сложности", то надо иметь возможность изменять каждый из них. Я читал, что есть типа "засады", потенциальные ямы, трудно проходимые для обучающихся алгоритмов, что есть игры с разным числом размерностей, которые тоже не всем обучающимся алгоритмам одинаково доступны, это всё я отношу к "сложностям" (неправильно?).

Зачем это всё: дело в том, что играющие программы будут нейросетями, с некоторыми дополнительными прибамбасами, оценить работу нейросети трудно, а прибамбасы отдельно от нейросети не работают, а я их отлаживать хочу.

Вот, т.е. я хотел бы увидеть в ответе продукт Вашей фантазии, но фантазии специалиста. Конкретные решения это долго, это уж я сам буду мучиться, не считаю себя в праве Ваше время отнимать. Тут должен добавить, что для меня это хобби, не работа.

Re: Спасибо, уточнение.

[avva.livejournal.com]

т.е. у вас есть несколько возможных обучающихся алгоритмов, основанных на нейросетях, и вы хотите их как-нибудь друг относительно друга оценивать. К сожалению, не зная, что эти алгоритмы собственно предназначены делать, какого рода информацию учить, какую функцию оптимизировать итд., все равно трудно сказать, как можно их друг с другом интересным образом сталкивать. Но по крайней мере из вашего объяснения ясно, что вам нужен специалист по machine learning - у меня, к сожалению, знания в этой области близки к нулю, так что вряд ли смогу вам чем-то конкретным помочь :(

Ну нет так нет.

[(Anonymous)]

Жаль, однако. Специалиста такого мне найти негде. Те, к которым я обращался, не выказывали интереса. Алгоритмы отличаются именно тем, что они (по замыслу) должны учиться играть в ЛЮБУЮ игру, абсолютно ничего вначале не зная о её правилах, и даже о том, что в ней является выигрышем, а что проигрышем. В этом вся идея. Т.е. я предполагаю существование некого универсального оценочного критерия успеха в любой игре и, шире, в любом виде деятельности. Понимаю, что это довольно дико звучит, но у меня есть основания (общефилософского плана). Что делать, мысли не всегда приходят в те головы, которые для них профессионально предназначены. И знаний не хватает, и приходится целый день совсем другими вещами заниматься...