Квантовые компьютеры очень хороши для выборочных распределений, которые мы не знаем, как делать выборки с использованием классических компьютеров. Например, если f - булева функция (от до - 1 , 1 ), которая может быть вычислена за полиномиальное время, то с квантовыми компьютерами мы можем...
Меня интересует проблема упаковки идентичных копий (2-мерных) прямоугольников в выпуклый (2-мерный) многоугольник без перекрытий. В моей задаче вы не можете поворачивать прямоугольники и можете предполагать, что они ориентированы параллельно осям. Вам только что дали размеры прямоугольника и...
Этот вопрос был перенесен из Cross Validated, потому что на него можно ответить на теоретической бирже информатики. Мигрировал 8 лет назад . У меня есть довольно уникальная проблема, которую я хочу решить, и я надеюсь, что кто-то здесь может дать мне некоторое представление о том, как лучше всего...
Задача «Не все равно kkk -SAT» (NAE kkk -SAT), учитывая набор CCC предложений над набором XXX булевых переменных, так что каждое предложение содержит не более kkk литералов, спрашивает, существует ли истинное присвоение переменных таким образом, чтобы каждое предложение содержит, по крайней мере,...
В настоящее время этот вопрос не очень подходит для нашего формата вопросов и ответов. Мы ожидаем, что ответы будут подтверждены фактами, ссылками или опытом, но этот вопрос, скорее всего, вызовет дебаты, споры, опрос или расширенное обсуждение. Если вы считаете, что этот вопрос можно улучшить и,...
Может кто-нибудь предложить хороший и недавний опрос по подсчету проблем и / или проблем, которые #P.
Мне было интересно, какие инструменты люди в этой области (теоретическая информатика) используют для создания презентаций. Поскольку большая часть компьютерных наук занимается не только написанием статей, но и презентациями, я подумал, что это будет важный мягкий вопрос. Это вдохновлено предыдущим...
Вдохновленный обширными иерархиями, присутствующими в теории сложности, я подумал, существуют ли такие иерархии и для систем типов. Однако два примера, которые я обнаружил до сих пор, больше похожи на контрольные списки (с ортогональными функциями), а не на иерархии (с последовательно растущими и...
Я недавно получаю свои статьи, отклоненные из журналов (то есть, TALG), просто из-за отсутствия значительной разницы между журналом и версией (то есть, SODA). Основными причинами для меня, чтобы представить в журнал является его тщательный процесс рецензирования. Помимо этого, ограничение в 20...
Практически, для языка, который в конечном итоге может быть скомпилирован / преобразован в инструкции системного уровня, необходимо ли, чтобы это была контекстно-свободная грамматика? пример: все ли языки программирования / написания сценариев являются контекстно-свободными грамматиками? Java...
Известно, что гамильтонов цикл (для краткости Хэм) NP-полон, а планарный цикл Хэма NP-полон. Доказательство для плоского цикла Хэма не из цикла Хэма. Есть ли хороший гаджет, который с учетом графа G заменит все пересечения некоторым плоским гаджетом, чтобы у вас был планарный граф G 'такой, что G...
Рассмотрим выпуклое тело KKK центром в начале координат и симметричное (т. Е. Если x∈Kx∈Kx\in K то −x∈K−x∈K-x\in K ). Я хочу найти другое выпуклое тело LLL такое, что K⊆LK⊆LK\subseteq L и следующая мера минимизируется: f(L)=E(xT⋅x−−−−−√)f(L)=E(xT⋅x)f(L)=\mathbb{E}(\sqrt{x^T \cdot x}), гдеxxx-...
Вдохновленный этим вопросом , каковы основные проблемы и существующие решения, которые нуждаются в улучшении в (теоретической) области распределенных систем. Что-то вроде протоколов членства, согласованности...
Я пытаюсь найти, насколько близки и , когда и является константой, не зависящей от n (поэтому ). Моя оценка такова: whp, но я не смог доказать это.E [ t w ( G ) ] G ∈ G ( n , p = c / n ) c > 1 E [ t w ( G ) ] = Θ ( n ) t w ( G ) ≤ E [ t w ( G ) ] + o ( n...
В квантовых вычислениях нас часто интересуют случаи, когда группа специальных унитарных операторов G для некоторой d-мерной системы дает либо целую группу SU (d) в точности, либо даже просто приближение, обеспечиваемое плотным покрытием SU (d). Группа конечного порядка, такая как группа Клиффорда...
Проблема Halting гласит, что невозможно написать программу, которая может определить, останавливается ли другая программа, для всех возможных программ ввода . Тем не менее, я могу, конечно, написать программу, которая может вычислить время выполнения программы вроде: for(i=0; i<N; i++) { x = 1;...
Мы знаем, что максимальный независимый набор (MIS) трудно аппроксимировать с коэффициентом для любого если P = NP. Какие существуют специальные классы графов, для которых известны лучшие алгоритмы аппроксимации?N1 - ϵn1−ϵn^{1-\epsilon}ε > 0ϵ>0\epsilon > 0 Каковы графики, для которых известны...
Ясно, что сокращение от CLIQUE до k-Color, потому что они оба NP-Complete. Фактически, я могу построить один, составив сокращение от CLIQUE до 3-SAT с сокращением от 3-SAT до k-Color. Мне интересно, есть ли разумное прямое сокращение между этими проблемами. Скажем, сокращение, которое я мог бы...
Недавно я видел несколько статей об arxiv, которые ссылаются на систему доказательств под названием сумма квадратов. Может кто-нибудь объяснить, что такое доказательство суммы квадратов и почему такие доказательства важны / интересны? Как они связаны с другими алгебраическими системами...
Учитывая набор людей, я хотел бы сидеть их для последовательности блюд за столами размера . (Конечно, для каждого приема пищи достаточно столов, чтобы все .) Я бы хотел организовать это так, чтобы никто не делил стол с одним и тем же человеком дважды. Типичными значениями являются и и от 6 до 10...