Входные данные: набор из точек в и целое число .nnnR3R3\mathbb{R}^3k≤nk≤nk \le n Выход: наименьший ограничивающий прямоугольник, выровненный по оси объема, который содержит не менее из этих точек.kkknnn Мне интересно, если какие-либо алгоритмы известны для этой проблемы. Лучшее, что я мог...
В прошлом журналы были основным способом распространения и проверки научных / математических открытий. В некоторых областях они все еще есть. Тем не менее, в (теоретической) информатике эту роль почти полностью выполняют конференции и открытое распространение через Интернет (например, arxiv или...
Пусть , быть ориентированный ациклический граф , и пусть - функция маркировки отображения каждой вершины с меткой в некотором конечном алфавите . Запись, А топологическая сортировка из является взаимно однозначное от к (т.е., упорядочение в последовательности) таким образом, что всякий раз , когда...
Является ли Н ПP P= PP PNPPP=PPP\mathsf{NP^{PP}} = \mathsf{P^{PP}} ? Или, в более общем плане , Is Н ПP P⊆ PP P/ РолуNPPP⊆PPP/poly\mathsf{NP^{PP}} \subseteq \mathsf{P^{PP}/poly}
Меня интересуют комбинаторные свойства социальных сетей в виде графиков. Люди смотрели на такие вещи, как распределение степеней, коэффициент кластеризации и сжимаемость этих графиков. Один основной вопрос: действительно ли эти графики являются хорошими графами расширителей? Кто-нибудь проверял,...
Антицепь в DAG представляет собой подмножество ⊆ V вершин, попарно недостижим, а именно, нет v ≠ v ' ∈ таким образом, что v достижима из V ' в Е . Из теоремы Дилворта в теории частичного порядка известно, что если DAG не имеет антицепи размера k ∈ N , то она может быть разложена в объединение не...
Пусть язык и f : Σ ⋆ × Σ ⋆ → Σ ⋆ функция по двум параметрам со свойством, которое для всех x и y , f возвращает элемент из L тогда и только тогда, когда x и y являются элементами из L :LLLе: Σ⋆× Σ⋆→ Σ⋆f:Σ⋆×Σ⋆→Σ⋆f\colon {\Sigma^\star}\times\Sigma^\star\to\Sigma^\starxxxyyyfffLLLxxxyyyLLL...
Я читал опубликованные книги, статьи и статьи о квантовых вычислениях. Я обнаружил, что все материалы, которые я видел, вместо того, чтобы описывать квантовые врата от базовой физики до абстракции, изо всех сил стараются не говорить о деталях реализации квантовых ворот . Сначала я задал себе...
Рассмотрим следующую задачу: для заданной матрицы , индексов i , j ∈ { 1 , … , n } и целого числа a . Заменить M [ я , J ] по и вызвать новую матрицу M . Является ли p e r ( M ) > pM∈{−m,…,0,…,m}n×nM∈{−m,…,0,…,m}n×nM\in\{-m,\dots,0,\dots,m\}^{n\times...
Глядя на модели параметрического полиморфизма, мне интересно, почему используются рефлексивные категории графов ? В частности, почему они не включают реляционную композицию? При взгляде на модели все они, кажется, поддерживают естественное понятие реляционной композиции:...
В документе конференции, чтобы доказать -полноту проблемы, я написал глупое предложение: «Ясно, что проблема в N P. Поэтому мы докажем, что это N P -hard». На самом деле это было не совсем понятно. Это даже кажется открытой проблемой. Для целевой аудитории это не имеет большого значения, потому что...
Я программирую уже несколько лет, но очень незнаком с теоретической CS. Недавно я пытался изучать языки программирования и, как часть этого, проверку типов и вывод. Мой вопрос заключается в том, что если я пытаюсь написать программу для вывода и проверки типов для языка программирования, и я хочу...
Я пытаюсь понять линейную логику, чтобы лучше понять системы линейного типа. Однако, когда я прочитал правила, я не в состоянии получить интуицию позади него , как я сделал в модальной логике - □ A◻A\Box A означает требуются , как в Крипке кадров требуются для каждого достижимого мира [ ◊ является...
Пусть - любая конечная структура. Имеет ли его теории первого порядка Т : = Т Н ( ) имеют ограниченную кванторное ранг, в том смысле , что существует д ∈ N такое , что для всех ф Е Т с ц г ( φ ) > д существует φ ' ∈ T с д г ( ф ' ) ≤ д и ф ' ≡ ф ?AA\mathfrak{A} T:=TH(A)T:=TH(A) \mathfrak{T} :=...
Пусть GGG - общий оракул в смысле категории Коэна / Бэра. Пусть RRR случайный оракул. Существуют ли классы сложности A и B с AG=BGandAR≠BRAG=BGandAR≠BR\mathrm{A}^G=\mathrm{B}^G\quad\text{and}\quad\mathrm{A}^R\ne \mathrm{B}^R или наоборот,...
Я знаю, что исчисление конструкций сильно нормализуется, то есть у каждого выражения есть норма, которая не может быть бета, далее сокращена. Так что на самом деле это наиболее эффективное выражение, которое вычисляет то же значение, что и исходное выражение. Но в некоторых случаях нормализация...
В монадической логике первого порядка, также известной как монадический класс задачи решения, все предикаты принимают один аргумент. Аккерманн показал, что он может быть разрешен и НЕОБХОДИМО завершен . Однако такие проблемы, как SAT и SMT, имеют быстрые алгоритмы их решения, несмотря на...
В целом решение о том, имеет ли диофантово уравнение какое-либо целочисленное решение, эквивалентно проблеме остановки. Я считаю, что решение о том, имеет ли какое-либо решение квадратное диофантово уравнение, является NP-полным. Существует ли дополнительное ограничение на используемые уравнения,...
У меня есть набор из nnn двоичных векторов S={s1,…,sn}⊆{0,1}k∖{1k}S={s1,…,sn}⊆{0,1}k∖{1k}S = \{s_1, \ldots, s_n \} \subseteq \{0,1\}^k \setminus \{1^k\} и целевой вектор t=1kt=1kt = 1^k который является вектором «все единицы». Гипотеза: если ttt можно записать как линейную комбинацию элементов SSS...
Общий вопрос Обобщает ли теорема о пространственной иерархии неравномерное вычисление? Вот несколько более конкретных вопросов: Является ли ?L / ролу⊊ PSпA CЕ/ РолуL/poly⊊PSPACE/polyL/poly \subsetneq PSPACE/poly Для всех космических построимых функций , является D S Р С Е ( О ( е ( п ) ) ) / р о л...