Учитывая огромную базу данных разрешенных слов (отсортированных по алфавиту) и слово, найдите слово из базы данных, которая является ближайшей к данному слову с точки зрения расстояния Левенштейна. Наивный подход, конечно, состоит в том, чтобы просто вычислить левенштейновское расстояние между...
Гипотеза реконструкции говорит о том, что графы (по крайней мере, с тремя вершинами) определяются однозначно их вершинами удаленных подграфов. Этой гипотезе пять десятилетий. В поисках соответствующей литературы я обнаружил, что следующие классы графов, как известно, восстанавливаемы: деревья...
Редактировать: я сначала неправильно сформулировал свое ограничение (2), теперь оно исправлено. Я также добавил больше информации и примеров. С некоторыми коллегами, изучающими какой-то другой алгоритмический вопрос, мы смогли свести нашу проблему к следующей интересной проблеме, но мы не смогли...
Теория сложности, с помощью таких понятий, как NP-полнота, различает вычислительные задачи, которые имеют относительно эффективные решения, и те, которые трудноразрешимы. «Мелкозернистая» сложность призвана уточнить это качественное различие в количественном руководстве относительно точного...
В настоящее время я пытаюсь найти полные задачи EXPSPACE (в основном, чтобы найти вдохновение для сокращения), и я удивлен небольшим количеством ожидаемых результатов. Пока я нашел это, и у меня есть проблемы с расширением списка: универсальность (или другие свойства) регулярных выражений с...
Я читал во многих статьях, что определение постоянной Чигера графа является -hard. Это кажется народной теоремой, но я никогда не находил ни цитаты, ни доказательства для этого утверждения. Кому я должен отдать должное за это? В старой статье («Изопериметрические числа графов», J. Comb. Theory B,...
Может кто-нибудь предложить хороший и недавний опрос по подсчету проблем и / или проблем, которые #P.
В настоящее время биткойн имеет систему проверки работоспособности (PoW) с использованием SHA256. Другие хеш-функции используют графы доказательства работы системы, частичное обращение хеш-функций. Можно ли использовать проблему принятия решений в теории узлов, такую как распознавание узлов, и...
Меня интересует проблема упаковки идентичных копий (2-мерных) прямоугольников в выпуклый (2-мерный) многоугольник без перекрытий. В моей задаче вы не можете поворачивать прямоугольники и можете предполагать, что они ориентированы параллельно осям. Вам только что дали размеры прямоугольника и...
При постоянная , можно определить в линейное время, учитывая входной граф G , является ли его древесной шириной есть ≤ K . Однако, когда оба k и G даны в качестве входных данных, проблема NP-трудна. ( Источник ).k ∈ Nk∈Nk \in \mathbb{N}гGG≤ k≤k\leq kКkkгGG Однако, когда входной граф является...
Задача «Не все равно kkk -SAT» (NAE kkk -SAT), учитывая набор CCC предложений над набором XXX булевых переменных, так что каждое предложение содержит не более kkk литералов, спрашивает, существует ли истинное присвоение переменных таким образом, чтобы каждое предложение содержит, по крайней мере,...
Для фиксированного конечного алфавита , формальный язык над является регулярным , если существует детерминированный конечный автомат (ДКА) над , которая принимает ровно .L ΣΣΣ\SigmaLLLΣΣ\SigmaLΣΣ\SigmaLLL Я интересуюсь языками, которые «почти» регулярны в том смысле, что они могут распознаваться...
Я пытаюсь понять связь между изоморфизмом графов и проблемой скрытой подгруппы. Есть хорошая ссылка для
Некоторые из вас, возможно, следили за этим вопросом , который был закрыт из-за отсутствия уровня исследования. Итак, я извлекаю часть вопроса, которая находится на исследовательском уровне. Помимо «более простых» техник, таких как приведение к сортировке или задача, полная по EXPTIME, какие методы...
Я только что понял, что я предполагаю, что ответ на мой вопрос - «да», но у меня нет веской причины. Я предполагаю, что, возможно, существует сборщик мусора, который доказуемо вводит только замедление в худшем случае. Есть ли конкретная ссылка, которую я могу привести? В моем случае я работаю над...
Кто-нибудь знает ссылки, в которых четко прописана связь между алгоритмом объединения и гауссовым исключением? Меня особенно интересует связь между треугольными заменами и LU-разложениями. Уэйн Снайдер и Джин Галлиер упоминают эту аналогию в своей статье « Возвращение к объединению высшего порядка:...
Этот вопрос касается временной сложности алгоритма максимального потока Форда-Фулкерсона при использовании DFS для поиска путей расширения. Существует хорошо известный пример, показывающий, что при использовании DFS может потребоваться линейное число итераций в максимальном потоке, см., Например,...
Тензор является обобщение векторов и матриц на более высокие размеры и ранг тензора также обобщает ранг матрицы. А именно, ранг тензора является минимальным числом ранга один тензоров этой суммы . Вектор и матрица являются тензорами степени 1 и 2 соответственно.TTTTTTT Элементы в происходят из поля...
Когда я возился с неканоническим анализом LR, я придумал метод синтаксического анализа (с таблицами бесконечного размера, что делает его несколько непрактичным ), способный анализировать ровно однозначные грамматики за времени, и мне было интересно, возможно ли это сделать лучше:O(n2)O(n2)O(n^2)...
Мне было интересно, какие бумаги я должен прочитать, чтобы понять этот вопрос Неожиданная связь с другими областями математики, такими как алгебраическая геометрия или высшие когомологии. Возможно, даже область математики еще не разработана. Возможно, кто-то разработает совершенно новое направление...