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

[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

[spamsink.livejournal.com]

Очень хорошая статья, спасибо!

[faceted-jacinth.livejournal.com]

Слушайте, я что-то не могу представить, как выглядят доказывающие, что P=NP (а искать экземпляры влом). Там же это, "предоставьте программу, решающую SAT на 30 переменных, дальше будем смотреть" - какие вообще могут быть дискуссии? Или там особые алгоритмические гении, которые не умеют программировать?

[faceted-jacinth.livejournal.com]

* то есть на 128 переменных, конечно =)

there are such SAT tools...

[(Anonymous)]

MiniSAT , YICES and others from the SAT competition works well in various problems with up to several hundreds variables

there are such SAT tools...

[(Anonymous)]

MiniSAT , YICES and others from the SAT competition works well in various problems with up to several hundreds variables...or I'm missing smth?

Re: there are such SAT tools...

[faceted-jacinth.livejournal.com]

I think they do work in a sense "possibly can find an answer, especially if there is a lot of redundancy in a problem". But I believe that for each of them exists a problem that would require actual enumeration of all of the 2**128 points of the problem space. Well, maybe somehow reduced polynomially, but then again, what I'm saying is that it's quite unlikely that any algorithm devised by a crank could handle a generic one-solution randomly generated SAT problem on 128 variables (I suppose there are well-known methods of spawning them) -- and if it does, then he is not an ignorable-by-definition crank, even if he believes that he solved something more important.

[illy-drinker.livejournal.com]

Вот несколько устаревшее, но интересное введение в PCP (пару лет назад нашли гораздо более короткое доказательство)
там дано одно неплохое доказательство и очень ясно показано для чего нужна PCP
http://www2.informatik.hu-berlin.de/~hougardy/paper/almss.pdf

Re: there are such SAT tools...

[(Anonymous)]

I see...yes, redundancy matters...Just for fun I've checked the SAT website:

http://baldur.iti.uka.de/sat-race-2008/downloads/SAT-Race-2008-Presentation.pdf

they have been solving instances with 11M variables and 32M clauses :)

[avva.livejournal.com]

Ну, наверное поэтому в частности обычно "доказывают" !=. Хотя в принципе можно представить неконструкривное доказательство =, хоть это и весьма маловероятно конечно (впрочем, = само по себе исключительно маловероятно). Например, что-то типа: предположим, что P!=PSPACE, возьмем язык в PSPACE\P и машину, его вычисляющую, будем каким-то способом последовательно строить приближающие ее машины в P, так что каждая следующая получается какой-то сложной конструкцией из предыдущей, и докажем неконструктивно, что этот процесс стабилизируется на каком-то шагу, неизвестно каком.

[avva.livejournal.com]

Спасибо!

[ygam.livejournal.com]

Спасибо.

[flaass.livejournal.com]

Я как-то придумал не совсем невероятную схему неконструктивного доказательства:
http://flaass.livejournal.com/462683.html
Все равно невероятно, конечно, но есть шансы, что так можно доказать полиномиальность изоморфизма графов.

[avva.livejournal.com]

Забавно, да.

[avva.livejournal.com]

Всегда пожалста.

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

[(Anonymous)]

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

[ltwood.livejournal.com]

Люди, верящие в P=NP, чаще возятся с многогранниками задач и оценивают плотности их графов.

http://www.ozon.ru/context/detail/id/3826570/

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

[avva.livejournal.com]

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

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

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

[(Anonymous)]

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

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

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

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

[avva.livejournal.com]

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

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

[(Anonymous)]

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