Вопросы с тегом «np»

Существует множество попыток доказать либо либо , и, естественно, многие люди задумываются над этим вопросом, имея идеи для доказательства того или иного направления.P ≠ N PP = N Pпзнак равноNп\mathsf{P} = \mathsf{NP} P ≠ N Pп≠Nп\mathsf{P} \neq \mathsf{NP} Я знаю, что есть подходы, которые, как...

У меня есть общее понимание проблемы и я понимаю, что если бы это было абсолютно «доказано», чтобы быть правдой с предоставленным решением, это открыло бы дверь для решения многочисленных проблем в области компьютерных наук.п= NпP=NPP=NP Мой вопрос: если бы кто-то опубликовал неоспоримое,...

Существуют ли NP-полные задачи, которые доказали алгоритмы субэкспоненциального времени? Я спрашиваю об общих входных данных, я не говорю о конкретных особых случаях здесь. Под субэкспоненциальным я подразумеваю порядок роста над полиномами, но менее экспоненциального, например,...

Есть ли известные проблемы в (а не в P ), которые не являются N P Complete? Насколько я понимаю, в настоящее время нет известных проблем, когда это так, но это не исключено как возможность. NPNп\mathsf{NP}Pп\mathsf{P}NPNп\mathsf{NP} Если есть проблема , которая является (а не Р ) , но не Н Р - с о...

Мой коллега и я только что нажали несколько заметок одного из наших профессоров. В примечаниях говорится, что есть задачи, которые можно решить за полиномиальное время (относятся к классу PF), но которые НЕ поддаются проверке за полиномиальное время (НЕ относятся к классу NPF). Чтобы уточнить эти...

Когда я объяснял доказательство Бейкера-Гилла-Соловая, что существует оракул, с которым мы можем иметь, , и оракул, с помощью которого мы можем иметь P ≠ N P другу, возник вопрос, почему такие методы плохо подходят для доказательства проблемы P ≠ N P , и я не мог дать удовлетворительный ответ.P = N...

Многим пришло в голову, что во всех NPNP\textbf{NP} полных доказательствах, которые я читал (которые я помню), всегда тривиально показать, что проблема в NPNP\textbf{NP} , и показать, что это NPNP\textbf{NP} жесткая, является ... трудной частью , Какие NPNP\textbf{NP} полные проблемы это те, чьи...

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

Так что я понимаю идею, что решение проблемы определяется как Есть ли путь P такой, что стоимость ниже, чем C? и вы можете легко проверить это, проверив полученный вами путь. Однако что, если нет пути, который соответствует этим критериям? Как бы вы проверили ответ «нет», не решив проблему TSP с...

Возможно ли, что и мощность совпадает с мощностью ? Или означает, что и должны иметь разные мощности?P≠NPP≠NP\mathsf{P} \not = \mathsf{NP}PP\mathsf{P}NPNP\mathsf{NP}P≠NPP≠NP\mathsf{P} \not =

Теорема Галуа эффективно говорит, что нельзя выразить корни многочлена степени> = 5, используя рациональные функции коэффициентов и радикалов - разве нельзя считать, что это говорит о том, что для данного многочлена нет детерминированного алгоритма для нахождения корней? Теперь рассмотрим...

Проводились ли какие-либо исследования сложности доказательства решения проблемы P = NP? Если нет, учитывая отсутствие прогресса в решении этой проблемы, было бы неразумно предполагать, что любое доказательство, которое решает проблему P = NP, потребует суперполиномиального числа...

Если действительно равен , как это улучшит наши алгоритмы, чтобы быстрее вычислять целые числа? Другими словами, какое понимание даст нам этот факт для лучшего понимания целочисленной факторизации?PP{\sf P}NPNP{\sf...

Я уверен, что кто-то думал об этом раньше или сразу же отклонил это, но почему теория дихотомии Шефера наряду с теоремой Махани о разреженных множествах не подразумевает P = NP? Вот мои рассуждения: создайте язык который равен SAT, пересекаемому бесконечным разрешимым разреженным множеством. Тогда...

Из этого поста я узнал, что в стеке есть поток, и есть несколько относительно быстрых алгоритмов для просеивания интервала чисел, чтобы увидеть, есть ли в этом интервале простое число. Тем не менее, означает ли это, что общая проблема решения: (Существует ли простое число в интервале?) В P. (Было...

Это мой первый пост после пассивного использования в течение некоторого времени. Я хотел бы задать несколько вопросов, если можно. Я не математик, но мой вопрос относится к области математики / информатики. В частности, проблема P против NP. Я знаю, что это проблема, которую элитные профессионалы...

Мой лектор сделал заявление Любая конечная задача не может быть NP-полной В то время он говорил о судоку, который сказал что-то вроде того, что для судоку 8х8 существует ограниченный набор решений, но я не могу точно вспомнить, что он сказал. Я записал записку, которую цитировал, но до сих пор не...

Я только что прочитал несколько страниц в книге Сипсера «Введение в теорию вычислений о проблеме почтовой корреспонденции» и думаю, что PCP на самом деле находится в NP. Сертификатор составляет: для конфигурации входного ворса конкатенации т 1 , т 2 , . , , , t n как строка t и конкатенация b 1 ,...

Я читал о NPC и его связи с PSPACE, и я хотел бы знать, могут ли проблемы NPC быть детерминированно решены с использованием алгоритма с наименьшим требованием к полиномиальному пространству, но потенциально с экспоненциальным временем (2 ^ P (n), где P - полиномиальный). Более того, может ли оно...

Мне интересно это на основании нескольких мест в Интернете, которые называют co- серьезной открытой проблемой ... но я не могу найти никаких указаний на то, является ли это тем же, что проблема ...Н П П = Н ПNP=NP=\sf NP=NPNP\sf NPP=NPP=NP\sf...