Dr. K. L. Metlov (dr_klm) wrote,
Dr. K. L. Metlov
dr_klm

Categories:

Числа Рамсея (Ramsey numbers)

Как большой любитель вечеринок (и, одновременно, большой нелюбитель квантовокомпьютерной ахинеи ;-) я не мог спокойно пропустить вот эту статью из последнего PRL (ее там даже назвали новостью недели). Оказывается, ученые придумали новый алгоритм для адиабатического квантового компьютера (которого не существует, в любом более-менее строгом смысле этого слова). Еще немного, и можно будет за новости физики выдавать изыскания об особенностях использования прыжковых сверхсветовых двигателей в червоточинах пространства. :-)

Но, вернемся к нашим вечеринкам (которые, к сожалению, в связи с окончанием череды праздников, подходят к некоторому промежуточному перерыву). Как мы уже здесь обсуждали, запрограммировать квантовый компьютер легко. Это можно сдедать здесь и сейчас для широчайшего класса комбинаторных задач. В том числе, конечно, и для нахождения чисел Рамсея. Вы скажете, что у размерность решаемых таким способом на обычном компьютере задач ограничена ? Да, но размерность задач, решаемых на современных квантовых компьютерах задач ограничена еще больше. Помните, как мы решали весной при помощи нашего "квантового компьютера" нонограммы, используя тысячи q-bit ? О таком масштабе современная квантовокомпьютерная наука может только мечтать, поскольку реальных идей: как реализовать такой масштабный КК -- нет. Пока они мечтают, Вы можете легко решать комбинаторные задачи здесь и сейчас. Большие/небольшие -- понятие относительное. По крайней мере, гораздо бОльшие, чем можно решить наивным перебором, при сравнимой затрате усилий на написание программы.

Представьте себе, что Вы огранизуете вечеринку. Вы, хотите, чтоб на веченинке у Вас была компания друзей (в количестве m человек), которые все друг друга знают или группа людей (из n человек), которые друг с другом не знакомы. Сколько минимально нужно пригласить людей (даже если мы о них ничего наперед не знаем), чтоб с гарантией была либо вот такая дружная компания (наперед заданного размера, m), либо скучающие по углам незнакомки (в определенном количестве, n). Вот это число и есть число Рамсея: R(m,n). Как его вычислить ?

Принцип простой. Для N человек построим полный граф из N вершин. Полный, значит все вершины соединены со всеми. Такой граф будет иметь N*(N-1)/2 ребер. Ребрам поставим в соответствие q-bitы нашего квантового компьютера. Тем самым мы как бы говорим, что ребро в графе может как бы одновременно присутствовать (люди знакомы между собой) и отсутствовать (люди не знакомы). Тоесть мы не знаем наперед -- знакомы люди или нет. Ну, как кот у Шредингера... Дальше мы задаем вопрос -- существуют ли конфигурации графа (конкретные определенные значения q-bit), такие что утверждение Рамсея нарушается (т.е. не существует как компании размера m так и клуба незнакомцев размером n). Для маленьких графов контр-примеры будут. Но, начиная с некоторого размера N, окажется, что для любых значений q-bit (т.е. конфигурации знакомств) утверждение будет выполнено. Значит, это и будет число Рамсея.

Сложность, как Вы понимаете, заключается в том, что количество всех возможных вариантов знакомств/незнакомств растет с увеличением N экспоненциально (конкретно как 2N(N-1)/2). Для рассмотрения (без перебора, который в данном случае провести не реально) такого количества вариантов и нужен квантовый компьютер (который мы, как и в прошлый раз, с успехом заменим построением BDD).

Сделаем мы это, как и впрошлый раз, в три счета. На счет раз вычислим все возможные выборки k элементов из множества N элементов, используя классический алгоритм из Книги. На счет два, вычислем ребра, которые остаются в исходном полном N-графе после удаления k вершин, соответствующих конкретной выборке. И, наконец, на счет три, непосредственно сформулируем утверждение Рамсея и поищем (для возрастающих N) к нему контр-примеры. Все эти программы вместе с Makefile можно скачать здесь (для компиляции потребуется библиотека BuDDy, libbdd-dev в Debian).

Последняя программа работает следующим образом (параметры m и n устанавливаются в исходном тексте).
$ ./ramsey2 
Looking for Ramsey number R(3,4)=
Considering complete 4-graph, which has 6 edges.
There are 40 not satisfying graphs
The number 4 is NOT the Ramsey number R(3,4). Continuing search.
Considering complete 5-graph, which has 10 edges.
There are 322 not satisfying graphs
The number 5 is NOT the Ramsey number R(3,4). Continuing search.
Considering complete 6-graph, which has 15 edges.
There are 2812 not satisfying graphs
The number 6 is NOT the Ramsey number R(3,4). Continuing search.
Considering complete 7-graph, which has 21 edges.
There are 13842 not satisfying graphs
The number 7 is NOT the Ramsey number R(3,4). Continuing search.
Considering complete 8-graph, which has 28 edges.
There are 17640 not satisfying graphs
The number 8 is NOT the Ramsey number R(3,4). Continuing search.
Considering complete 9-graph, which has 36 edges.
There are 0 not satisfying graphs
Eureka ! R(3,4)=9

Как видите, для данного простенького примера нам потребовалось 36 q-bit. Это не много, но это потому что m и n взяты небольшими. Вы можете взять больше. ;-)

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

Чтобы поставить рекорд -- нужно думать. Рекордные результаты получены не перебором (простым или квантовым) а, прежде всего, аналитически. Возможно, когда нибудь удастся найти для этих числел простую формулу.
Tags: popul, sci
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 17 comments