Вопросы с тегом «reference-request»

11
Имеет ли система F с парами сильные свойства нормализации и сокращения объекта?

Во многих учебниках легко найти доказательства сокращения предмета и строгой нормализации для Системы F, а также иногда есть определения Системы F с парами, где (t, r) - это термин, а не только кодировка. Вопрос в том, что будет ссылкой на эту...

11
Вычисление макс. H-свободных множеств

В графе независимое множество - это подмножество вершин, которое не содержит ребра в качестве индуцированного подграфа. Проблема нахождения наибольших независимых множеств в графе является фундаментальным и сложным в этом вопросе. Давайте рассмотрим более общий вопрос поиска (размера) наибольшего...

11
Люди смотрят на циклическое гнездо в логических цепях?

В то время как EE старшекурсник я посетил некоторые лекции, которые представили хорошую характеристику булевых схем с точки зрения, сколько у них вложенных циклов. По своей сложности булевы схемы часто считаются дагами, но в реальных аппаратных циклах это обычное явление. Теперь, по модулю...

11
Нижние оценки для недетерминированного многопартийного общения

Это продолжение моего предыдущего вопроса о нижних границах связи для частичных булевых функций . Может ли кто-нибудь предложить какую-либо ссылку на нижние границы для недетерминированного многопартийного общения? Я просматривал статьи в этой области, но все, кажется, демонстрируют разделение...

11
Минимальная масса леса данной мощности

Этот вопрос был мотивирован вопросом, заданным на stackoverflow . Предположим, вам дано корневое дерево (т. Е. Есть корень, а у узлов есть дочерние элементы и т. Д.) На n узлах (обозначены 1 , 2 , … , n ).TTTNnn1 , 2 , … , n1,2,…,n1, 2, \dots, n Каждая вершина имеет неотрицательный целочисленный...

11
Пространство средней сложности

Я пытаюсь найти проблемы, сложность которых в среднем случае была проанализирована. Более конкретно, мне интересно знать, есть ли какие-либо проблемы с доказанной нижней границей сложности пространства, которая является суперлинейной, и особенно, если есть какие-либо проблемы с анализом среднего...

11
Восстановление наклона оцифрованной линии

Была ли работа по восстановлению наклона отрезка линии после его оцифровки? Конечно, нельзя делать это с идеальной точностью; то, что нужно, - это метод получения из оцифрованной линии интервала возможных уклонов. (Понятие оцифрованной строки, которую я использую, - это Розенфельд: набор пар где...

11
Класс сложности NEXP

У меня есть проблема, которая находится в NEXP и также может быть решена с помощью чередующегося ТМ, использующего экспоненциальное время и только одно чередование (начиная с экзистенциального состояния).NPNP^{\text{NP}} Что-нибудь известно о NEXP ? Это равно NEXP или какому-то другому классу?...

11
Ссылки на языки программирования на основе условной логики

Условная логика - это логика, которая дополняет традиционную логическую импликацию модальными операторами, соответствующими другим понятиям условия (например, условная причина To гласит: « вызывает« B », или вероятностное обусловливание « », которое читается как « данный »).A□→BA◻→BA\;...

11
Нахождение конечной модели

Я знаю, что вопрос «имеет ли формула первого порядка модель» вообще неразрешим.φϕ\phi Может ли кто-нибудь дать мне ссылку или книгу, которая даст ответ для конечных моделей. Если у меня есть формула первого порядка , можно ли имеет ли конечную модель? Я почти уверен, что вопрос хорошо известен, но...

11
Учитывая, что PDA M такой, что L (M) находится в DCFL, строят DPDA N такой, что L (N) = L (M)

Можно ли построить алгоритм, который принимает в качестве входных данных автомат сокращения вместе с обещанием, что язык, принятый этим автоматом является детерминированным контекстно-свободным языком и выводит детерминированный автомат нажатия который принимает именно принятый язык на ?MMMЛ (...

11
Нелокальные игры и квантовая коммуникация

В настоящее время я ищу хороший справочный материал о нелокальных играх с полезными аспектами квантовой коммуникации. Например, я знаю, что нелокальные игры хороши для более низкой сложности связи, а также для обеспечения безопасности протоколов QKD. То, что я хотел бы знать, - это какие-то большие...

11
Подмодульные функции: запрос ссылки

Я был бы очень заинтересован ссылками на теорию субмодулярных функций (от основ до продвинутых). В частности, я изучаю приближения к сложным задачам оптимизации и хочу развить свои основы субмодулярных функций, поскольку они имеют отношение к задачам оптимизации, которые я изучал. Заранее...

11
Сложность уникального st-Connectivity

Я хотел бы знать, может ли быть решена следующая проблема в (недетерминированное пространство журнала):NLNL\mathsf{NL} Для ориентированного графа с двумя выделенными вершинами s и t существует ли единственный путь из s в t в G ?s tGGGssstttт гssstttGGG Я чувствую, что он, вероятно, находится в...

11
Варианты художественной галереи с попарной видимостью?

Задача традиционной художественной галереи устанавливает регион и охранников с некоторым представлением о видимости и требует минимального количества охранников, которые необходимо разместить, чтобы увидеть весь регион. Кто-нибудь когда-нибудь смотрел варианты художественной галереи, где область...

11
Границы аппроксимирующих частотных моментов

Пусть - последовательность целых чисел, где каждый . Для , пусть, - й момент частоты определяется какa j ∈ { 1 , 2 , … , n } i ∈ { 1 , 2 , … , n } m i = | { j : a j = i } | Кa1,a2,…,ama1,a2,…,ama_1, a_2,\dotsc, a_maj∈{1,2,…,n}aj∈{1,2,…,n}a_j \in \{1,2,\dotsc,n\}i∈{1,2,…,n}i∈{1,2,…,n}i \in...

11
На мерных многообразиях и решетках

РЕДАКТИРОВАТЬ (Тара B): Я все еще был бы заинтересован в ссылке на доказательство этого, так как я должен был доказать это сам для моей собственной статьи. Я ищу доказательство теоремы 4, которое появляется в этой статье: Бесконечная иерархия пересечений контекстно-свободных языков Лю и Вейнера....

11
Нахождение двойственного графа

Согласно книге «Топологическая теория графов» Гросса и Такера, учитывая клеточное вложение графа на поверхность (под «поверхностью» я подразумеваю здесь сферу с некоторыми ручками , а ниже S n относится к сфере с ровно n ручками), можно определить двойной мультиграф, рассматривая грани исходного...

11
Последние публикации по NP? = CoNP вопрос

Меня интересует вопрос, является ли NP равным coNP или нет. Я был бы очень признателен за советы о хороших публикациях по этой теме. Для справки, я знаю, что этот вопрос тесно связан с вопросом о том, равен ли P NP или нет (например, если NP! = CoNP, то P! = NP). Ура,...