В квантовой теории информации расстояние между двумя квантовыми каналами часто измеряется с использованием алмазной нормы. Существует также ряд способов измерения расстояния между двумя квантовыми состояниями, таких как расстояние следа, точность и т. Д. Изоморфизм Ямиолковского обеспечивает...
Пусть f(n)f(n)f(n) будет временем выполнения задачи на входе размера в худшем случае nnn. Давайте сделаем задачу немного странной, установив f(n)=n2f(n)=n2f(n) = n^2 для n=2kn=2kn=2k но f(n)=nf(n)=nf(n) = n для n=2k+1n=2k+1n=2k+1 . Итак, какова нижняя граница проблемы? Насколько я понял, это просто...
Кажется, известно, что для того, чтобы найти ответ на запрос по реляционной базе данных , нужно время , и невозможно избавиться от показателя степени,QQQDDD|D||Q||D||Q||D|^{|Q|}|Q||Q||Q| Поскольку может быть очень большим, мы задаемся вопросом, почему базы данных вообще работают на практике.DDD...
Меня интересуют модели случайных графов, которые похожи на графы реальных компьютерных сетей. Я не уверен, что общая хорошо изученная модель ( n вершин, каждое возможное ребро выбрано с вероятностью p ) подходит для изучения реальных компьютерных сетей (не так ли?).G ( n , p )G(n,p)G(n,p)Nnnпpp...
Обратимые вычисления - это вычислительная модель, которая допускает только термодинамически обратимые операции. В соответствии с принципом Ландауэра, который гласит, что стирание небольшого количества информации высвобождает джоулей тепла, это исключает переходные функции, которые не являются...
В своей статье (стр. 503) Гарей и Джонсон замечают: ... может существовать NP-полная задача, которая не является NP-полной в строгом смысле и не разрешима алгоритмом псевдополиномиального времени ... Кто-нибудь знает некоторые возможные проблемы со свойствами, упомянутыми выше? Я думаю, что...
Существуют ли ссылки, которые предоставляют подробности о нижних границах схем для конкретных сложных задач, возникающих в криптографии, таких как целочисленный факторинг, задача простого / составного дискретного логарифма и ее вариант над группой точек эллиптических кривых (и их абелевых...
Каковы лучшие ресурсы для поиска вакансий на должности преподавателей в теории CS? Существует ли какой-то один веб-сайт или список рассылки, который является достаточно полным? В настоящее время у меня сложилось впечатление, что нужно использовать различные ресурсы, чтобы получить исчерпывающий...
Rn\mathbb{R}^n⟨⋅,⋅⟩\langle \cdot, \cdot \ranglemmv1,v2,…,vmv_1, v_2, \ldots, v_mx∈Rnx \in \mathbb{R}^nмин я ⟨ х , v я ⟩ mini⟨x,vi⟩\min_i \langle x, v_i \rangleО ( п т )O(nm)O(nm) п = 2 n=2n = 2O ( войти 2 м )O(log2m)O(\log^2 m) Единственное, что я могу придумать, это следующее. Непосредственным...
Вопрос прост и прям: для фиксированного , сколько (разных) языков принято DFA размером n (то есть nnnnnnnnnn состояний)? Я официально заявлю это: Определите DFA как , где все как обычно и δ : Q × Σ → Q (возможно, частичная) функция. Нам нужно установить это, поскольку иногда только полные функции...
Прогнозировать фондовый рынок сложно! Может ли TCS сделать это мнение более формальным? Недавно я начал немного думать о финансах, и мне было интересно, как знание TCS может помочь. Хедж-фонды и инвестиционные фирмы, кажется, все время используют алгоритмическую торговлю, машинное обучение и ИИ,...
Справочная информация: Чао Сюй некоторое время назад опубликовал следующий вопрос: « Существуют ли какие-либо известные алгоритмы сортировки сравнения, которые не сводятся к сортировке сетей, так что каждый элемент сравнивается раз?O(logn)O(logn)O(\log n) ». Кажется, мы немного застряли в...
В настоящее время я заинтересован в получении (или построении) и изучении формул 3-CNF, которые являются неудовлетворительными и имеют минимальный размер. То есть они должны состоять из как можно меньшего числа предложений (предпочтительно m = 8) и как можно меньшего числа различных переменных (n =...
Как известно, вычисление постоянной Чигера для графика , также известного как изопериметрическая постоянная (поскольку это, по сути, минимальное отношение площади / объема), является NP-полным. Вообще это приблизительно. Мне интересно узнать, известны ли точные полиномиальные алгоритмы для...
Пусть GGG - невзвешенный неориентированный граф с nnn вершинами и mmm ребрами. Можно ли предварительно обработать GGG и создать структуру данных размером m⋅polylog(n)m⋅polylog(n)m \cdot \mathrm{polylog}(n) чтобы он мог отвечать на запросы вида «расстояние между uuu и vvv » за время O (n)? Проблема...
Меня интересует сложность решения линейных уравнений по модулю k для произвольного k (и с особым интересом к простым степеням), а именно: Проблема. Для данной системы из линейных уравнений по неизвестным по модулю , существуют ли какие-либо решения?н кmmmnnnkkk В аннотации к своей статье Структура...
Предположим, у нас есть неориентированный взвешенный граф G=(V,E,w)G=(V,E,w)G = (V, E, w) (с неотрицательными весами). Предположим, что все кратчайшие пути в GGG единственны. Предположим, у нас есть эти пути (последовательности невзвешенных ребер), но мы не знаем саму G. Можем ли мы создать G ,...
У меня совсем недавно была дискуссия о машинах Тьюринга, когда меня спросили: «Машина Тьюринга получена из автоматов или наоборот»? Конечно, я не знал ответа, но мне любопытно узнать. Машина Тьюринга - это немного более сложная версия автоматов Push-Down. Исходя из этого, я предполагаю, что машина...
Вам дан граф с вершинами. Это может быть двудольный, если хотите. Существует наборов ребер (скажем, дизъюнкт). Меня интересует проблема нахождения как можно меньшего (или даже меньшего) подмножества , такого, чтобы индуцированный граф имел хотя бы одно ребро из каждого класса , для ,G = ( V,...
Рассмотрим следующую модель: n-битная строка r = r 1 ... r n выбирается случайным образом равномерно. Далее каждый индекс i∈ {1, ..., n} помещается в множество A с независимой вероятностью 1/2. Наконец, противнику разрешено, для каждого i∈A отдельно, перевернуть r i, если он этого хочет. Мой вопрос...