Два бинарных дерева поиска называются линейно эквивалентными, когда они сходятся в своих обходах по порядку. Следующая теорема объясняет, почему повороты деревьев так фундаментальны: Пусть A и B - бинарные деревья поиска. Тогда A и B линейно эквивалентны тогда и только тогда, когда они связаны...
Предположим, что вам дан набор из n точек на плоскости, и вы хотите проверить, образуют ли они выпуклый n-многоугольник, т. Е. Лежат ли все они на выпуклой оболочке. Мне было интересно, если кто-нибудь знает, как это сделать за время (nlogn), т. Е. Без вычисления...
Предположим, у нас есть множество S графов (конечных графов, но их бесконечное число) и группа перестановок P, которая действует на S. Экземпляр: перестановка p в P. Вопрос: существует ли граф g в S, который допускает автоморфизм p? Является ли эта задача NP-полной для некоторых множеств S? Было бы...
Формула Monotone-2CNF - это формула CNF, в которой каждое предложение состоит ровно из двух положительных литералов. Теперь у меня есть Монотонный-2CNF формула . Пусть S будет множеством удовлетворяющих заданий F. У меня также есть оракул O, который может дать следующую информацию:FFFSSSFFFOOO...
В рассматриваемом приложении мне необходимо знать сложность связи следующей проблемы: Для данного пусть S будет множеством целых чисел от 1 до n . Алиса, Боб и Кэрол каждый получает подмножество S , обозначенное A , B и C соответственно. Они хотят , чтобы проверить , является ли , B и C образуют...
Класс сложности PPAD обычно определяется указанием того, что End-Of-The-Line является PPAD-завершенным. End-Of-The-Line - это проблема поиска. Входные данные состоят из ориентированного графа, в котором у каждого узла максимальная и минимальная степени равны 1. Граф задается вычисляемой функцией...
Вопрос возник у меня, когда я получил ответ Даны Мошковиц на другую тему . Пусть будет языком NP , и пусть будет соответствующим отношением NP . Мы знаем, что существует некоторый полином такой, что:LLLрLрLR_Lппp ∀ x ∈ L ,, ∃ ж ∈0 , 1р ( | х | )( x , w ) ∈...
Справочная информация: В машинном обучении мы часто работаем с графическими моделями, чтобы представить функции плотности с высокой размерностью. Если отбросить ограничение на интеграцию плотности (суммы) в 1, мы получим ненормализованную графо-структурированную энергетическую функцию ....
Известно, что определение того, является ли данное триангулированное 3-многообразие 3-сферой, входит в NP посредством работы Сола Шлеймера в 2004 году: «Распознавание сфер лежит в NP» arXiv: math / 0407047v1 [math.GT] . Я задаюсь вопросом, было ли это установлено, чтобы быть законченным NP за...
Вопрос Что нового в чисто функциональных структурах данных со времен Окасаки? и эпический ответ jbapple, упомянутый с использованием списков различий в функциональном программировании (в отличие от логического программирования), что меня недавно интересовало. Это привело меня к поиску реализации...
Проблема сплетен в распределенных системах заключается в следующем. У нас есть граф с n вершинами. Каждая вершина v имеет сообщение m v, которое необходимо отправить всем узлам.GGGnnnvvvmvmvm_v Теперь мой вопрос в контексте специальной сетевой модели (мы предполагаем, что узел не имеет каких-либо...
Допустим, у нас есть однослойная прямая нейронная сеть с k входами и одним выходом. Он вычисляет функцию из , довольно легко увидеть, что она имеет по крайней мере ту же вычислительную мощность, что и A C 0 . Просто для удовольствия мы назовем набор функций, вычислимых однослойной нейронной сетью,...
Я имею опыт работы в теории / логике сложности (где большую часть времени занимает только один процесс) и в распределенных вычислениях (где есть процессов, и один или несколько могут со временем выйти из строя). Однако теперь я хочу сказать что-то о процессе, порождающем / создающем / порождающем...
Пусть быть мульти-мерный полином с коэффициентами над полем . Мультилинеаризация , обозначаемая , является результатом многократной замены каждого с на . Результат, очевидно, является полилинейным полиномом.р ( х 1 , ... , х п ) F р р х д я д > 1 х...
Существует два основных типа сбоев процессора в моделях распределенных вычислений: (1) Сбои: процессор останавливается и больше не запускается. (2) Византийские сбои: процессоры ведут себя соперничающе, злонамеренно. Мой вопрос: Каковы некоторые другие типы отказов процессора, которые были изучены,...
Я задал этот вопрос в перекрестной проверке вопросов и ответов, но, похоже, он связан с CS гораздо больше, чем со статистикой. Можете ли вы привести примеры алгоритмов машинного обучения, которые изучают статистические свойства набора данных, а не отдельные наблюдения, то есть используют...
Я искал о матричном умножении, поэтому я впервые посещал вики- алгоритмы умножения матриц, в ссылках я нашел статью, в которой утверждается, что используется алгоритм O ( n2л о г( н ) )О(N2Lограмм(N))O(n^2 log(n)) , я собираюсь прочитать статью, но она сложная и Уилл читает слишком много времени,...
Многие классы сложности, определенные с помощью машин Тьюринга, имеют определения в терминах однородных цепей. Например, P также может быть определен с использованием схем с однородным полиномиальным размером, и аналогично BPP, NP, BQP и т. Д. Могут быть определены с помощью однородных схем. Так...
Задача о гамильтоновом цикле (HC) состоит в том, чтобы найти цикл, который проходит через все вершины в данном неориентированном графе. Задача коммивояжера (TSP) состоит в том, чтобы найти цикл, который проходит через все вершины в данном графе, взвешенном по ребрам, и минимизирует общее...
При изучении различных методов доказательства нижних границ для распределенных алгоритмов мне пришло в голову, что следующий вариант теоремы Рэмси может найти применение - если это окажется правдой. Параметры: , K , n заданы, а затем N выбирается достаточно большим. Терминология: m- подмножество -...