В связи с загадкой Slither Link мне было интересно: предположим, что у меня сетка квадратных ячеек, и я хочу найти простой цикл ребер сетки, равномерно случайным образом среди всех возможных простых циклов.n×nn×nn\times n Один из способов сделать это - использовать цепь Маркова, состояния которой...
Проблема удовлетворенности является, конечно, фундаментальной проблемой в теоретической CS. Я играл с одной версией проблемы с бесконечным количеством переменных. \newcommand{\sat}{\mathrm{sat}} \newcommand{\unsat}{\mathrm{unsat}} Базовая настройка. Пусть непустое и, возможно, бесконечное множество...
Поскольку термин перегружен, сначала дается краткое определение. Poset - это множество наделенное частичным порядком ≤ . Для двух элементов a , b ∈ X , мы можем определить x ∨ y (join) как их наименьшую верхнюю границу в X и аналогично определить x ∧ y (meet) (join) как наибольшую нижнюю...
У меня есть два раздела [1…n][1…n][1 \ldots n] и я ищу расстояние редактирования между ними. Этим я хочу найти минимальное количество отдельных переходов узла в другую группу, которые необходимы для перехода из раздела A в раздел B. Например, расстояние от {0 1} {2 3} {4}в {0} {1} {2 3 4}будет два...
Рассмотрим следующую проблему: Входные данные : гиперплоскость ЧАС= { y ∈ RN:Tу = б }H={y∈Rn:aTy=b}H = \{ \mathbf{y} \in \mathbb{R}^n: \mathbf{a}^T\mathbf{y} = {b}\} , задается вектором a ∈ ZNa∈Zn\mathbf{a} \in \mathbb{Z}^n и b ∈ Zb∈Zb \in \mathbb{Z} в стандартном двоичном представлении. Выход : x...
Я задавал этот вопрос несколько недель назад в mathoverflow , но не получил ответа. Здесь под 3D-сеткой с длиной стороны я имею в виду граф G = ( V , E ) с V = { 1 , … , k } 3 и E = { ( ( a , b , c ) , ( x , y , z ) ) ∣ | а - х | + | б - у | + | сkkkG=(V,E)G=(V,E)G=(V,E)V={1,…,k}3V={1,…,k}3V=...
РЕДАКТИРОВАТЬ (Тара B): Я все еще был бы заинтересован в ссылке на доказательство этого, так как я должен был доказать это сам для моей собственной статьи. Я ищу доказательство теоремы 4, которое появляется в этой статье: Бесконечная иерархия пересечений контекстно-свободных языков Лю и Вейнера....
Hiroimono является популярной головоломкой Complete. Я заинтересован в вычислительной сложности связанной головоломки.NпNPNP Проблема в: Входные данные : заданный набор точек на квадратной сетке x n и целое число kNnnNnnКkk Вопрос : существует ли прямолинейный многоугольник (его стороны параллельны...
Сначала спросили по математике. Без ответов. Предположим, у меня есть плоский граф с плоским вложением, как мне найти разложение дерева? Каково оптимальное разложение дерева by- квадратной сетки? Не совсем уверен, как определить «оптимальный», но следует различать разложение с одним большим мешком...