Я разместил это ранее на MSE, но было предложено, что здесь может быть лучшее место, чтобы спросить. Теорема универсального приближения утверждает, что «стандартная многослойная сеть прямой связи с одним скрытым слоем, которая содержит конечное число скрытых нейронов, является универсальным...
Из того, что я понимаю (что очень мало, поэтому, пожалуйста, поправьте меня, где я ошибаюсь!), Теория языков программирования часто связана с "интуиционистскими" доказательствами. В моей собственной интерпретации, подход требует, чтобы мы серьезно относились к последствиям вычислений для логики и...
Некоторые из вас, возможно, следили за этим вопросом , который был закрыт из-за отсутствия уровня исследования. Итак, я извлекаю часть вопроса, которая находится на исследовательском уровне. Помимо «более простых» техник, таких как приведение к сортировке или задача, полная по EXPTIME, какие методы...
Рассмотрим следующую вычислительную задачу: мы хотим отобрать 3-SAT формулу из переменных (вариант: переменных предложений) относительно равномерного распределения вероятностей, при условии, что формула выполнима:NNnNNnммm Q1: может ли это быть эффективно достигнуто с помощью классического...
Каковы убедительные причины верить L ≠ PL≠PL\neq P ? L - класс алгоритмов лог-пространства с указателями на вход. Предположим, что L = P на данный момент. Как будет выглядеть алгоритм лог-пространства для P-полной задачи в общих...
Рассмотрим задачи оптимизации следующего вида. Пусть f(x)f(x)f(x) - вычислимая функция полиномиального времени, которая отображает строку xxx в рациональное число. Задача оптимизации заключается в следующем: что максимальное значение f(x)f(x)f(x) над nnn -битовый строки xxx ?...
Я знаю, что тривиально функция OR для переменных может быть точно представлена полиномом следующим образом: , который имеет степень .х 1 , ... , х п р ( х 1 , ... , х п ) р ( х 1 , ... , х п ) = 1 - П п я = 1 ( 1 - х я ) пNnnИкс1, … , ХNx1,…,xnx_1,\ldots, x_nр ( х1, … ,...
Для фиксированного конечного алфавита , формальный язык над является регулярным , если существует детерминированный конечный автомат (ДКА) над , которая принимает ровно .L ΣΣΣ\SigmaLLLΣΣ\SigmaLΣΣ\SigmaLLL Я интересуюсь языками, которые «почти» регулярны в том смысле, что они могут распознаваться...
Важная статья 2003 года Childs et al.представил «проблему соединенных деревьев»: проблему, допускающую экспоненциальное квантовое ускорение, которое не похоже ни на одну другую подобную проблему, о которой мы знаем. В этой задаче нам дан экспоненциально большой граф, подобный изображенному ниже,...
В настоящее время я пытаюсь найти полные задачи EXPSPACE (в основном, чтобы найти вдохновение для сокращения), и я удивлен небольшим количеством ожидаемых результатов. Пока я нашел это, и у меня есть проблемы с расширением списка: универсальность (или другие свойства) регулярных выражений с...
Многочлен является монотонной проекцией многочлена если = poly , и существует присваивание , что . Таким образом, можно заменить каждую переменную из на переменную или константу или так, чтобы полученный многочлен совпадал с . е(x1,…,xn)f(x1,…,xn)f(x_1,\ldots,x_n)m ( n ) π : { y 1 , … , y m } → { x...
Учитывая две строки x и y, я хочу создать DFA минимального размера, который принимает x и отклоняет y. Один из способов сделать это - перебор. Вы перечисляете DFA, начиная с самого маленького. Вы пробуете каждый DFA, пока не найдете тот, который принимает x и отклоняет y. Я хочу знать, есть ли...
Пусть L1,L2L1,L2L_1,L_2 будут двумя обычными языками, заданными NFA M1,M2M1,M2M_1,M_2 качестве входных данных. Предположим, мы хотели бы проверить, является ли L1∩L2≠∅L1∩L2≠∅L_1\cap L_2\neq \emptyset . Это можно сделать с помощью квадратичного алгоритма, который вычисляет автомат произведений...
Я читал во многих статьях, что определение постоянной Чигера графа является -hard. Это кажется народной теоремой, но я никогда не находил ни цитаты, ни доказательства для этого утверждения. Кому я должен отдать должное за это? В старой статье («Изопериметрические числа графов», J. Comb. Theory B,...
По мотивам комментария Фортнау к моему сообщению, доказательством того, что проблема изоморфизма графов не является NпNпNP -полным , и тем фактом, что G IгяGI является главным кандидатом в NпNпNP -проблеменную проблему (не NпNпNP -полное ни в ппP ), я заинтересованы в известных доказательств , что...
В настоящее время биткойн имеет систему проверки работоспособности (PoW) с использованием SHA256. Другие хеш-функции используют графы доказательства работы системы, частичное обращение хеш-функций. Можно ли использовать проблему принятия решений в теории узлов, такую как распознавание узлов, и...
При постоянная , можно определить в линейное время, учитывая входной граф G , является ли его древесной шириной есть ≤ K . Однако, когда оба k и G даны в качестве входных данных, проблема NP-трудна. ( Источник ).k ∈ Nk∈Nk \in \mathbb{N}гGG≤ k≤k\leq kКkkгGG Однако, когда входной граф является...
Теория сложности, с помощью таких понятий, как NP-полнота, различает вычислительные задачи, которые имеют относительно эффективные решения, и те, которые трудноразрешимы. «Мелкозернистая» сложность призвана уточнить это качественное различие в количественном руководстве относительно точного...
Доступ к оракулу обеспечит значительное, сверхполиномиальное ускорение для всего в (при условии, что набор не пуст). Тем не менее, не совсем ясно, сколько выиграет от этого доступа к оракулу. Конечно, ускорение в не может быть суперполиномиальным, но оно может быть полиномиальным. Например, можем...
Хорошо известно, что многие важные параметры графа показывают (сильную) концентрацию на случайных графах, по крайней мере, в некотором диапазоне вероятности границы. Некоторые типичные примеры: хроматическое число, максимальная клика, максимальный независимый набор, максимальное совпадение, номер...