Поскольку термин перегружен, сначала дается краткое определение. Poset - это множество наделенное частичным порядком ≤ . Для двух элементов a , b ∈ X , мы можем определить x ∨ y (join) как их наименьшую верхнюю границу в X и аналогично определить x ∧ y (meet) (join) как наибольшую нижнюю...
Статья Фишера за этот месяц напомнила мне, как мало я знаю об искусстве кратких структур данных и алгоритмах их использования. Для тех, кто не знает о сжатых структурах данных: Учитывая комбинаторную структуру, с (n) различными конфигурациями и известным «полезным» представлением . Существует ли...
Как хорошо известно, PARITY не может быть выполнено в многоразмерных схемах с постоянной глубиной, и на самом деле схемы с постоянным углублением требуют количества входов EXP. А как насчет схем QUANTUM? а) Можно ли выполнить PARITY с помощью квантового контура, который имеет постоянную глубину и...
Я понимаю, что полнота Тьюринга требует неограниченной памяти и неограниченного времени. Однако в этом сервисе существует ограниченное количество атомов, что ограничивает память. Например, даже если иррационально, нет способа сохранить более определенного числа цифр, даже если все атомы во...
Можно ли эффективно задавать ациклический ориентированный граф для следующих операций?G(V,E)G(V,E)G(V,E) isConnected(G,a,b)isConnected(G,a,b)isConnected(G,a,b) : определяет, существует ли путь в от узла до узлаGGGaaabbb link(G,a,b)link(G,a,b)link(G,a,b) : добавляет ребро из в в графеaaabbbGGG...
Что если что-либо известно о параметризованной сложности вычисления числа пересечений графа (наименьшее число кликов, необходимых для охвата всех его ребер)? Давно известно, что он является NP-полным, и это, очевидно, FPT, потому что у него есть ядро: если вы можете покрыть граф кликами, то...
Моя идея карьеры мечты - это карьера в промышленных исследованиях, где можно решать сложные задачи, а также найти практическое применение. В связи с этим, преследует ли докторскую степень в TCS (меня интересуют такие темы, как распределенные / параллельные алгоритмы, онлайн-алгоритмы), плохая идея?...
как можно показать, какова связь между «гипотезой об уникальных играх» и «теоремой PCP»? Как объяснить, что «гипотеза об уникальных играх» является более сильной формой «теоремы...
В теории автоматов (конечных автоматов, автоматов с выталкиванием, ...) и в сложности существует понятие «неоднозначность». Автомат является неоднозначным, если существует слово по крайней мере, с двумя различными принимающими сериями. Машина является неоднозначной, если для каждого слова принятого...
Я ищу простой пример двух систем перехода, которые эквивалентны LTL, но не эквивалентны трассе. Я прочитал доказательство того, что Эквивалентность трассировки является более тонкой, чем Эквивалентность LTL, в книге «Принципы проверки моделей» (Baier / Katoen), но я не уверен, что действительно...
Гиперкомпьютер относится к моделям вычислений, которые невозможно моделировать с использованием машин Тьюринга. (Гиперкомпьютеры не обязательно физически реализуемы!) Некоторые гиперкомпьютеры имеют доступ к ресурсу, который позволяет решить проблему остановки для стандартных машин Тьюринга....
Хорошо известно, что если вы бросите n шаров в n корзин, то в самой загруженной корзине, скорее всего, будет шариков. В общем, можно спросить о шарах в корзинах. В статье из RANDOM 1998, опубликованной Раабом и Стегером, это подробно рассматривается, показывая, что с ростом вероятность того, что...
Мне сказали, что есть несколько хороших алгоритмов полиномиального времени для аппроксимации числа простых путей в ориентированном графе от заданной начальной вершины до заданной конечной вершины t . Кто-нибудь знает хорошую ссылку на эту тему?sssTTt Справочная информация: подсчет точного числа...
У меня есть два раздела [1…n][1…n][1 \ldots n] и я ищу расстояние редактирования между ними. Этим я хочу найти минимальное количество отдельных переходов узла в другую группу, которые необходимы для перехода из раздела A в раздел B. Например, расстояние от {0 1} {2 3} {4}в {0} {1} {2 3 4}будет два...
Метод отрицательного противника ( ) - это SDP, характеризующий сложность квантового запроса. Это обобщение широко используемого метода противника ( A D V ), и оно преодолевает два барьера, мешающих противнику:A D V±ADВ±ADV^\pmA D VADВADV Барьер тестирования свойств: если все 0-экземпляры находятся...
Недавно я прочитал доказательство, которое намеревалось показать, что проблема была сильно NP-трудной, просто сводя ее (за полиномиальное время) от сильно NP-трудной задачи. Это не имело никакого смысла для меня. Я бы подумал, что вам нужно будет показать, что любые числа, использованные в...
Недавно я был на конференции, поддерживаемой ACM. Во время банкета организаторы конференции рассказали нам о будущем и прошлом конференции. Они сказали нам, что во время конференции 2010 года была потеря 5000 $. Они показали нам бюджет предыдущей конференции, где мы могли видеть, что на ACM было...
Каковы наиболее известные методы циклической свертки длины над небольшим полем, т.е. когда | F | « П ? Меня особенно интересуют поля постоянного размера или даже . Общие утверждения и ссылки об асимптотической эффективности высоко ценятся.nnn|F|≪n|F|≪n|\mathbb{F}| \ll nF=F2F=F2\mathbb{F} =...
задира Поскольку проблема длинная, здесь есть особый случай, который отражает ее суть. Проблема: Пусть A - детриминистический алгоритм для 3-SAT. Является ли проблема полного моделирования алгоритма A (на каждом экземпляре задачи). P-Space сложно? (Точнее, есть ли основания полагать, что эта задача...
- это множество точек на плоскости. Случайная точка x ∉ S задается на той же плоскости. Задача состоит в том, чтобы отсортировать все y ∈ S по евклидову расстоянию между x и y .SSSx∉Sx∉Sx \notin Sy∈Sy∈Sy \in Sxxxyyy Бездумный подход состоит в том, чтобы вычислить расстояния между и y для всех y ∈...