Я интересно, если есть полиномиальный алгоритм для «2-SAT с XOR-отношений». И 2-SAT, и XOR-SAT находятся в P, но является ли их комбинация? Пример ввода: 2-SAT часть: (a or !b) and (b or c) and (b or d) XOR часть: (a xor b xor c xor 1) and (b xor c xor d) Другими словами, вход представляет собой...
Означает ли существование неразрешимых проблем непосредственную непредсказуемость физических систем? Давайте рассмотрим проблему остановки, сначала мы построим физический UTM, скажем, используя обычную конструкцию на основе схем. Тогда не может быть никакой разрешимой физической теории, которая...
Есть ли способ вычислить размер максимального соответствия в невзвешенном двудольном графе более эффективно (например, быстрее), чем вычисление максимального соответствия? Это длинный путь, но часто это интересная проблема, чтобы избежать одноразовых вычислений, подобных этим. мотивация Проблема ,...
В настоящее время я посещаю курс параллельного программирования в моем университете, и недавно мы начали говорить о концепции монитора. Хотя я понимаю необходимость взаимного исключения, я не понимаю, почему я бы использовал для этого монитор. Насколько я понимаю, монитор гарантирует, что в...
Закрыто . Этот вопрос основан на мнении . В настоящее время он не принимает ответы. Хотите улучшить этот вопрос? Обновите вопрос, чтобы ответить на него фактами и цитатами, отредактировав этот пост . Закрыто 4 года назад . Я увлекаюсь математической элегантностью и строгостью, и сейчас ищу такую...
Зоопарк Сложности определяет как класс задач решения, решаемых детерминированной машиной Тьюринга за линейное время.LINLINLIN LIN⊆PLIN⊆PLIN \subseteq P Поскольку HORN-SAT разрешим в (как указано в алгоритмах линейного времени для проверки выполнимости формул рогового высказывания (1984)...
Я задавался вопросом, почему ленты / ленты не являются частью формального определения машины Тьюринга. Рассмотрим, например, формальное определение машины Тьюринга на странице Википедии . Определение, следующее за Хопкрофтом и Уллманом, включает в себя: конечный набор состояний , ленточный алфавит...
Я пытаюсь получить общее представление о важности наименьшей фиксированной точки (lfp) в анализе программы. Например, абстрактная интерпретация, кажется, использует существование lfp. Многие исследовательские работы по анализу программ также сосредоточены на поиске наименее фиксированной точки....
В проблемах удовлетворения ограничений эвристика может использоваться для повышения производительности решателя бактрекинга. Три обычно используемых эвристики для простых решателей обратного отслеживания: Минимальные оставшиеся значения (сколько значений все еще допустимо для этой переменной)...
В основном проблема заключается в следующем: для набора положительных чисел найти минимальное число , которое не является делителем ни одного элемента из , т. .SSSdddSSS∀x∈S, d∤x∀x∈S, d∤x\forall x \in S,\ d \nmid x Обозначим n=|S|n=|S|n = |S|и C=max(S)C=max(S)C = \max(S) . Рассмотрим функцию...
Тестовый раунд Google Hash Code 2015 ( формулировка проблемы ) задал вопрос о следующей проблеме: вход: сетка с несколькими отмеченными квадратами, порог , максимальная площадьT ∈ N A ∈ NMMMT∈ NT∈NT \in \mathbb{N}A ∈ NA∈NA \in \mathbb{N} Выход: наибольшая возможная площадь множества...
Пытаясь понять взаимосвязи между кодированием Хаффмана, арифметическим кодированием и дистанционным кодированием, я начал думать о недостатках кодирования Хаффмана, связанных с проблемой дробной битовой упаковки . То есть, предположим, что у вас есть 240 возможных значений для символа, и вам...
Учитывая подмножество декартового произведения из двух конечных множеств, я хочу найти его минимальное покрытие множествами, которые сами являются декартовыми произведениями.я× Jя×JI \times J Например, учитывая произведение между и , я могу наблюдать подмножество и постарайтесь покрыть это...
Алгоритм Шора часто используется в качестве аргумента. Он может решить проблему факторизации быстрее, чем любой известный алгоритм для классических компьютеров. Тем не менее, у нас нет доказательств того, что классические компьютеры также не могут эффективно вычислять целые числа. Есть ли...
Я хочу выразить следующее ограничение в целочисленной линейной программе: Y= { 01если х = 0если x ≠ 0.y={0if x=01if x≠0.y = \begin{cases} 0 &\text{if } x=0\\ 1 &\text{if } x\ne 0. \end{cases} У меня уже есть целочисленные переменные и мне обещают, что - 100 ≤ x ≤ 100 . Как я могу выразить...
Ответ на Programmers.SE характеризует эссе Кука ( объекты не АТД ) , как говорят Объекты ведут себя как характеристическая функция над значениями типа, а не как алгебра. Объекты используют процедурную абстракцию, а не абстракцию типа ADT обычно имеют уникальную реализацию в программе. Когда у...
Я изо всех сил пытаюсь понять цель универсального и экзистенциального количественного определения типов. Я играю с написанием игрушечного языка, основанного на исчислении конструкций . Я читал о Морте и Хенке, чтобы помочь мне лучше понять. Я не понимаю, почему у CoC есть и лямбда, и полная...
В качестве забавного проекта я работал над реализацией C # Ричарда Корфа - Поиск оптимальных решений для кубика Рубика с использованием шаблонных баз данных. https://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf У меня действительно это работает, я просто пытаюсь улучшить...
Название говорит само за себя, но мне любопытно, потому что не очевидно, как доказатель теорем получил название «Изабель». Это было названо в честь человека? Я не мог узнать по некоторым поискам...
Есть ли простой способ понять, почему NP находится в EXPTIME? Мне кажется априори возможным, что может существовать проблема, для решения которой требуется сверхэкспоненциальное время, но решение которой можно проверить за полиномиальное...