Factorials

[Nataly-Mak]

Pavlovsky в сообщении #706921 писал(а):

Для меня конкурс закончен. Больше ничего делать не буду. Пусть работает компьютер. Если что то найдет, хорошо. Нет, значит судьба.

Э, нет, вы обещали 24,47 баллов

[Pavlovsky]

Программы продолжают работать. Надеюсь, 2-3 результата они еще найдут.

[dimkadimon]

Nataly-Mak в сообщении #706925 писал(а):

Э, нет, вы обещали 24,47 баллов

Вообще он обещал 24.5+

-- 07.04.2013, 21:01 --

Xaositect в сообщении #706870 писал(а):

$n$ растет быстрее, чем любой $\log^k n$.

A вроде понял. Значит $n\log n$ тоже растет быстрее чем $\log^k n$. Но это нам ничего не говорит для вопроса NP!=P.

[Xaositect]

dmd в сообщении #706882 писал(а):

А нельзя ли подробнее пояснить взаимосвязь с проблемой P?=NP. Разве все NP-задачи сводятся к задаче этого конкурса? Если да, то где оно это доказательство сводимости? Если вдруг в данном контексте решение задачи сводимости не нужно делать, то это тоже надо отдельно пояснить - почему так?

Вкратце, дело обстоит так: во-первых, речь идет не о классической проблеме $\mathbf{P}\neq \mathbf{NP}$, а об одном из ее алгебраических вариантов --- соотношении алгебраических аналогов $\mathbf{P}$ и $\mathbf{NP}$ в модели Валианта без констант. Для этой модели полной задачей является вычисление перманента матрицы (матрицы с рациональными элементами, элементарными операциями в алгоритме считаются операции над рациональными числами, алгоритмы рассматриваются неуниформные, то есть можно рассматривать совершенно разные алгоритмы для разных размеров матрицы). В отличие от детерминанта, который вычисляется быстро с помощью алгоритма Гаусса, сложность вычисления перманента предположительно экспоненциальна по размеру матрицы. Далее, если мы рассмотрим программу, которая вычисляет перманент рациональной матрицы, то, подав на вход матрицу из всех единичек, мы получим программу, определяющую $n!$. Подробнее см. Buergisser, on defining integers and proving arithmetic circuit lower bounds, препринт http://eccc.hpi-web.de/eccc-reports/200 ... index.html

[dmd]

Xaositect в сообщении #707023 писал(а):

речь идет не о классической проблеме $\mathbf{P}\neq \mathbf{NP}$, а об одном из ее алгебраических вариантов --- соотношении алгебраических аналогов $\mathbf{P}$ и $\mathbf{NP}$ в модели Валианта без констант.

Спасибо. Сразу такой вопрос возникает. Если будет дан какой-то ответ в неклассической постановке, то как это повлияет на классическую проблему соотношения $\mathbf{P}$ и $\mathbf{NP}$? И прокомментируйте мой скепсис, пожалуйста. Выражение "алгебраический аналог $\mathbf{P}$" звучит как-то околонаучно. В моём представлении любой алгоритм алгебраичен, и наоборот - любая алгебраическая матмодель алгоритмична. Т.е. по сути это одно и то же. Нет ни каких "аналогов" $\mathbf{P}$ либо $\mathbf{NP}$. Корректными рассуждениями можно показать, что задача относится к какому-то из этих двух классов. В конце рассуждений неизбежно возникнет вопрос о сведении всего класса задач к этой текущей. Или всё сложнее?

[Xaositect]

Под "алгебраическим аналогом $\mathbf{P}$" понимается класс многочленов, вычисляемых схемами полиномиального размера. Более точно:
Задачей или $p$-последовательнсотью будем называть последовательность $f_n(x_1,\dots, x_{k(n)})$ многочленов, число переменных и степень которых полиномиально зависит от индекса (термин "задача" в таком смысле в литературе не применяется, но мне кажется уместным).
Неветвящейся программой над полем $F$ с входом $(x_1,\dots,x_k)$ без констант называется последовательность многочленов, в которой каждый элемент есть либо свободная переменная $x_i$, либо получен из предыдущих сложением, вычитанием или умножением. Программы можно еще предмтавлять в виде графов, они тогда называются арифметическими схемами. Последний многочлен называется результатом программы, формальной степенью программы называется максимальная степень монома результата с учетом нулей при больших степенях, которые могут получиться при сложении многочленов с противоположными коэффициентами. Семейством программ для задачи $f_n$ называется последовательность программ $\Gamma_n$, результатами которых являются многочлены $f_n$.
Класс $\mathbf{VP}^0_F$ - это класс всех задач $f_n$, для которых существует семейство вычисляющих их программ, размер и формальная степень которых полиномиальны по $n$.
Класс $\mathbf{VNP}^0_F$ - класс задач, предстаимых в виде $f_n(x_1,\dots,x_{k(n)}) = \sum\limits_{\mathbf{y}\in \{0,1\}^{s(n)}} g_n(x_1,\dots,x_{k(n)}, y_1,\dots, y_{s(n)})$ с $g\in\mathbf{VP}^0_F$ и $s(n) = \mathrm{poly}(n)$.
Классы $\mathbf{VP}$ и $\mathbf{VNP}$ определяются аналогично, но разрешается еще операция умножения на произвольную константу из поля $F$.

По-поводу связи с классической постановкой. Одна из основных проблем здесь - неуниформность модели Валианта (для разных $n$ используются разные программы), так что в классической постановке классам $\mathbf{VP}$ и $\mathbf{VNP}$ соответствуют неуниформные классы $\mathbf{P}/\mathrm{poly}$ и $\mathbf{NP}/\mathrm{poly}$. Известно, что $\mathbf{VP}_F = \mathbf{VNP}_F$ для конечного поля $F$ влечет $\mathbf{P}/\mathrm{poly} = \mathbf{NP}/\mathrm{poly}$, и в предположении обобщенной гипотезы Римана то же верно для $F = \mathbb{Q}$. Известно также, что $\mathbf{P}/\mathrm{poly} = \mathbf{NP}/\mathrm{poly}$ влечет схлопывание полиномиальной иерархии до 2 уровня, то есть $\mathbf{NP}^{\mathbf{NP}^{\mathbf{NP}}} =\mathbf{NP}^{\mathbf{NP}}$

[dimkadimon]

Xaositect, cпасибо за подробное объяснение. Тут все гораздо сложнее чем я думал.

[Nataly-Mak]

Нашла два числа с новым рекордом количества решений в 10 шагов, это числа 19550 и 19551.
Для числа 19550 прервала программу, когда было найдено более 6500 решений, а для 19551 - более 4000 решений. Побоялась, что у меня памяти не хватит, чтобы все решения найти. До конца работы программы было ещё далеко.
Так и не знаю, сколько на самом деле решений в 10 шагов для этих чисел и какое из них "рекорднее"

Найдено оптимальное решение для 25!
Это чудесное решение, которое искали сообща
Великолепный образец сотрудничества, слаженной работы. После конкурса покажу это очень интересное решение.

Ещё был такой интересный момент...
Когда я нашла оптимальное решение для 30!, сразу же проверила домножение на 31, 31*32, 31*32*33 и т.д. Ничего не нашла.
Но!... проверила только от одного решения, а у меня два решения для 30!, которые очень мало отличаются друг от друга. И вот решила проверить домножение от второго решения. К моему удивлению, мгновенно выскочило решение для домножения на 31*32*33=32736.
Так удалось улучшить решение для 33!, хотя всего только на один шаг. И то хлеб

Может быть, кому-то пригодится этот нехитрый приём.

[dimkadimon]

Nataly-Mak в сообщении #707599 писал(а):

Нашла два числа с новым рекордом количества решений в 10 шагов, это числа 19550 и 19551.

А почему 10 шагов? Ведь для этих чисел есть решения в 8 шагов:
1, 2, 3, 5, 25, 28, 784, 782, 19550
1, 2, 4, 8, 7, 49, 57, 343, 19551

-- 09.04.2013, 14:10 --

Nataly-Mak в сообщении #707599 писал(а):

Это чудесное решение, которое искали сообща

А какая у вас команда?

[Nataly-Mak]

dimkadimon в сообщении #707624 писал(а):

Nataly-Mak в сообщении #707599 писал(а):

Нашла два числа с новым рекордом количества решений в 10 шагов, это числа 19550 и 19551.

А почему 10 шагов? Ведь для этих чисел есть решения в 8 шагов:
1, 2, 3, 5, 25, 28, 784, 782, 19550
1, 2, 4, 8, 7, 49, 57, 343, 19551

Я знаю
Мне для формулы нужны решения и в 8, и в 9, и в 10 шагов.
Нашла для 19550: в 8 шагов - 1 решение, в 9 шагов - 245 решений; для числа 19551: 4 решения в 8 шагов и 538 решений в 9 шагов.
Всё это проверила; нужны ещё решения в 10 шагов. А вот с этими решениями проблема - очень уж их много.

Цитата:

А какая у вас команда?

Команда у меня очень хорошая
Я уже писала, что со мной по-прежнему whitefox.
Другого участника назову после конкурса (если он не будет возражать).

[Nataly-Mak]

Цитата:

19 24.10 Vladimir Chirkov Bobruisk, Russia 8 Apr 2013 11:22

Как же это я вчера прозевала такой важный момент
Vovka17
поздравляю с вступлением в клуб 24+
Теперь и десятка недалеко

[Pavlovsky]

Nataly-Mak в сообщении #707739 писал(а):

Теперь и десятка недалеко

Резкий рывок вверх сделала пара швейцарцев. А ведь еще несколько дней назад были совсем рядом. Увы вместе с собой швейцарцы увезли 10-е и 11-е место.

6 24.84 Albert Graells Rovira Zürich, Switzerland 9 Apr 2013 21:43
11 24.69 Lucien Pech Zürich, Switzerland 9 Apr 2013 17:47

[Nataly-Mak]

В этом конкурсе попасть хотя бы в топ-20 большой успех.

Цитата:

1 25.00 Tomas Rokicki Palo Alto, California, United States 22 Feb 2013 03:36
2 25.00 Hermann Jurksch Recklinghausen, Germany 14 Mar 2013 23:03
3 25.00 Martin Piotte Montreal, Quebec, Canada 17 Mar 2013 19:36
4 25.00 Walter Trump Nuremberg, Germany 27 Mar 2013 21:27
5 24.89 Gil Dogon Jerusalem, Israel 12 Mar 2013 17:55
6 24.84 Albert Graells Rovira Zürich, Switzerland 9 Apr 2013 21:43
7 24.84 Lars Nagel Mainz, Germany 2 Apr 2013 17:08
8 24.79 John Morris Simi Valley, California, United States 3 Apr 2013 23:47
9 24.78 Hanhong Xue Fuzhou, China 22 Mar 2013 00:14
10 24.72 Siva Dirisala Foster City, California, United States 3 Apr 2013 08:39
11 24.69 Lucien Pech Zürich, Switzerland 9 Apr 2013 17:47
12 24.47 Dmitry Kamenetsky Adelaide, Australia 14 Mar 2013 22:17
13 24.46 Michael Hürter Saarbrücken, Germany 7 Apr 2013 13:43
14 24.42 Valery Pavlovsky Ekaterinburg, Russia 7 Apr 2013 04:37
15 24.41 Ashley Wood Guildford, United Kingdom 4 Apr 2013 22:13
16 24.37 Andy Sloane Sunnyvale, California, United States 8 Feb 2013 21:39
17 24.23 Herbert Kociemba Darmstadt, Germany 30 Mar 2013 09:09
18 24.22 Valentin Dobrota Constanta, Romania 7 Feb 2013 11:05
19 24.10 Vladimir Chirkov Bobruisk, Russia 8 Apr 2013 11:22
20 24.02 Alessandro Amici Roma, Italy 9 Apr 2013 12:04

Россиян здесь всего двое

Кстати, все тут имеют 24+
Престижный клуб
Наша команда, увы, в этот клуб не входит.

[Nataly-Mak]

У нас пока ещё играют:

Цитата:

29 23.70 Viktor Polesov Moskow, Russia 10 Apr 2013 13:04
138 17.00 Yurii Sigolaev Saint Petersburg, Russia 10 Apr 2013 19:52

Хорошо идёт Yurii Sigolaev, прямо семимильными шагами
Как я понимаю, он вводит только оптимальные решения. Значит, ему осталось найти всего 8 решений. Здорово!
Но при этом он ведь может получить решения для недостающих N из тех решений, которые у него уже есть, хотя и не оптимальные. Однако это даст ему дополнительные баллы.

Если бы я была администратором конкурса, учредила бы специальный приз - за наивысшую активность Играть так играть!

[Pavlovsky]

11 24.69 Lucien Pech Zürich, Switzerland 9 Apr 2013 17:47
12 24.53 Valery Pavlovsky Ekaterinburg, Russia 11 Apr 2013 03:21
13 24.47 Dmitry Kamenetsky Adelaide, Australia 14 Mar 2013 22:17

Австралия пройдена. У dimkadimon было достаточно времени, чтобы защитить свою позицию. Я ждал долго когда он поднимется вверх.

Увы 11-е место для меня недосигаемо. В лушем случае, за оставшееся время, получу еще два результата.