Утверждения, которые подразумевают

22

Это своего рода открытый вопрос, за который я заранее прошу прощения.

Существуют ли примеры утверждений, которые (казалось бы) не имеют ничего общего со сложностью или машинами Тьюринга, но ответ на них подразумевал бы ? $\mathbf{P}\neq \mathbf{NP}$

cc.complexity-theory complexity-classes p-vs-np Доминик ван дер Зипен
источник

4

Был бы «Не существует системы доказательств для логики высказываний, в которой каждая тавтология

φ

$\varphi$ имеет доказательство полиномиальной (по длине

φ

$\varphi$ ) длины». считать, или это слишком близко к сложности из-за полиномиальной границы?

Ян Йоханнсен

Так как нет «точных» ответов на мой вопрос, ваша гипотеза будет иметь значение ... Я просто ищу удивительные и разные точки зрения на проблему P против NP

Доминик ван дер Зипен

4

Я думаю, описательная сложность дает несколько примеров. Например, утверждение «существуют свойства (упорядоченных структур), которые могут быть выражены экзистенциальными формулами второго порядка, которые не могут быть выражены универсальными формулами второго порядка», эквивалентно ответу @ JanJohannsen, тогда как «существуют свойства (упорядоченных структур), которые можно выразить с помощью экзистенциальные формулы второго порядка , которые не могут быть выражены с помощью первых формул порядка с оператором наималейшим неподвижной точки»именно

P \neq N P

$\mathsf P\neq\mathsf{NP}$ . Это считается?

Дамиано Мазза

«

N \neq 1

$\mathbf{N}\neq 1$ и

P \neq 0

$\mathbf{P}\neq 0$ ». * rimshot *

Дэвид Ричерби

1

Аналогичный вопрос cstheory.stackexchange.com/questions/9806/…

Pay

14

Система доказательств логики высказываний называется полиномиально ограниченной , если каждая тавтология $\varphi$ имеет доказательство в системе полиномов длины по длине $\varphi$ .

Заявление «Там нет полиномиально ограниченная пропозициональной системы доказательств» эквивалентно с помощью классического результата Кук и Reckhow , так что подразумевает . $\mathsf{NP} \neq \mathsf{co}\text-\mathsf{NP}$ $\mathsf{P} \neq \mathsf{NP}$

Ян Йоханнсен
источник

2

Я думаю, что (по определению системы пропозициональных доказательств для

-полного языка тавтологий) предположение («Не существует системы доказательств для логики высказываний, в которой каждая тавтология

имеет доказательство полинома (в длина

) длина ") почти идентична допущению

; и , следовательно , почти идентичны при условии ,

.

c o N P

$\mathsf{coNP}$

φ

$\varphi$

φ

$\varphi$

N P \neq c o N P

$\mathsf{NP}\neq\mathsf{coNP}$

N P \neq P

$\mathsf{NP}\neq\mathsf{P}$

Иддо Цамерет

@IddoTzameret: но мы должны знать , что тавтология

-полных, верно? И это не тривиально. Я предполагаю, что этот пример только подтверждает интерес к наличию «естественных» полных задач: мы можем говорить о классах сложности, не говоря явно о машинах, используемых для их определения (что, по-видимому, и задает ОП). Или, может быть, я неправильно понял ваш комментарий ...

c o N P

$\mathsf{coNP}$

Дамиано Мазза

@Damiano, я думаю, что факт, что TAUT является coNP-полным, тривиален, в том смысле, что это подразумевается его определением и NP-полнотой SAT.

Иддо Цамерет

@IddoTzameret, хорошо, но вы согласны, что

-полнота SAT не тривиальна, верно? Это по сути то, что я говорил. Я имею в виду, что между утверждением «

», сформулированным в терминах машин Тьюринга, и их временем выполнения и положением «нет полиномиально ограниченной системы доказательства пропозиций», я вижу нетривиальный пробел, они определенно не Выглядит "почти идентично". Этот пробел заключается в полноте TAUT или SAT, как вам угодно, но он есть. Ты не согласен?

N P

$\mathsf{NP}$

N P \neq c o N P

$\mathsf{NP}\neq\mathsf{coNP}$

Дамиано Мазза

1

Да, свойство «

является доказательством

» должно проверяться за полиномиальное (в

и

) время. И оно должно быть обоснованным и полным, т. Е. Формула должна иметь доказательство, если это тавтология.

p

$p$

φ

$\varphi$

| p |

$|p|$

| φ |

$|\varphi|$

Ян Йоханнсен

12

Теория геометрической сложности (GCT) (также [1]) пока не упоминается. это большая амбициозная программа для соединения P против NP с алгебраической геометрией. например, краткий обзор опроса. Понимание подхода Малмулей-Сохони к P против NP , Regan:

Стабильность - это неформальное понятие «не хаотичности», которое превратилось в основную ветвь алгебраической геометрии под влиянием Д. А. Мамфорда, среди прочего. Ketan Mulmuley и Milind Sohoni [MS02] отмечают, что многие вопросы о классах сложности могут быть переформулированы как вопросы о природе групповых действий над определенными векторами в определенных пространствах, которые кодируют проблемы в этих классах. Этот обзор объясняет их структуру с точки зрения непрофессионала и пытается оценить, действительно ли этот подход добавляет новую силу атакам на вопрос «П. против НП».

также краткий обзор в разделе "Новая надежда?" в состоянии проблемы P против NP , Fortnow (2009)

Mulmuley и Sohoni свели вопрос об отсутствии алгоритмов полиномиального времени для всех NP-полных задач к вопросу о существовании алгоритма полиномиального времени (с определенными свойствами) для конкретной задачи. Это должно дать нам некоторую надежду, даже перед лицом проблем (1) - (3).

Тем не менее, Малмулей считает, что на выполнение этой программы потребуется около 100 лет, если она вообще будет работать.

[1] Объяснение теории геометрической сложности в стиле Википедии (tcs.se)

ВЗН
источник

Спасибо за привлечение GCT! Кажется, это касается моей собственной проблемы [M], но я раньше не сталкивался с ней. «Эти вычислительные проблемы могут быть охарактеризованы их симметриями. Программа нацелена на использование этих симметрий для доказательства нижних оценок».

DukeZhou

10

Следующий результат Raz (неуловимые функции и нижние границы для арифметических схем, STOC'08) нацелен на (а не непосредственно на ), но он может быть достаточно близок для OP: $VP\neq VNP$ $P\neq NP$

Полиномиальное отображение является -элюзивным, если для каждого полиномиального отображения степени , Image ( ) Image ( ). $f:\mathbb F^n \to \mathbb F^m$ $(s, r)$ $Γ : \mathbb F^s → \mathbb F^m$ $r$ $f$ $\not⊂$ $Γ$

Для многих установок параметров , явные конструкции неуловимых полиномиальных отображений подразумевают сильные (до экспоненциального) нижних границ для общих арифметических схем. $n, m, s, r$

Иддо Цамерет
источник

Что такое полиномиальное отображение? Вы имеете в виду "полином"? Вы имеете в виду «вычислимая функция за полиномиальное время»? Что-то другое?

DW

2

Это просто последовательность из

полиномов, каждый из которых имеет одинаковые

переменных; следовательно, он определяет отображение из

в

.

m

$m$

n

$n$

F^{n}

$\mathbb{F}^n$

F^{m}

$\mathbb{F}^m$

Иддо Цамерет

9

есть несколько побочная / более недавно изученная область сложности, называемая сложностью графов, которая изучает, как большие графы строятся из меньших графов с использованием операций И и ИЛИ ребер. У Юкны хороший опрос . в частности, с использованием единиц «звездных графов» есть ключевая теорема, см. p20 замечание 1.18 (теорема технически сильнее, чем ниже, и фактически подразумевает ): $P \ne NP/poly$

Мы уже знаем (теорема 1.7), что существуют двудольные графы G сложности звезды ; на самом деле, это почти все графики. С другой стороны, из леммы о сильном увеличении следует, что даже нижняя граница для сколь угодно малой константы сложности звезды в явном $n × m$ $Star(G) = (nm/ \log n)$ $Star(G) ≥ (2+c)n$ $c > 0$ граф с имел бы большие последствия в сложности схемы: такой граф дал бы явную булеву функцию требующую схемы экспоненциального (в числе переменных) размера! (Напомним, что для булевых функций даже суперлинейные нижние оценки пока неизвестны.) В частности, если граф таков, что смежность вершин в может быть определена недетерминированной машиной Тьюринга, работающей во временном полиноме в двоичная длина $n×m$ $G$ $m = o(n)$ $f_G$ $\log_2 nm$ $G$ $G$ кодов вершин, то нижняя грань при сколь угодно малой постоянной будет означатьчто . Таким образом, звездная сложность графов охватывает одну из самых фундаментальных проблем информатики. $log_2 n$ $Star(G) ≥ (2 + c)n$ $c > 0$ $P \ne NP$

ВЗН
источник

6

Я думаю , что вы имеете в виду

. Утверждение

уже тривиально известно.

P / p o l y ⊅ N P

$P/poly \not \supset NP$

P \neq N P / p o l y

$P \neq NP/poly$

Йонатан N

@YonatanN

верно?

P \neq N P / p o l y

$P\neq NP/poly$

Т ....

Ага. Известно, что даже P / poly содержит проблемы вне P, такие как унарная проблема остановки.

Йонатан N

Спасибо за ссылку Jukna! «Сложность - одно из важнейших научных явлений нашего времени. В этой главе мы рассмотрим сложность графиков».

DukeZhou

1

Как насчет Филиппа Маймина

« Рынки эффективны тогда и только тогда, когда утверждают P = NP »?

RB
источник

3

Утверждения и «доказательства» в этой статье не выглядят строгими, и аргументы кажутся мне недостающими. Вы читали эту статью?

Рахул Савани

Я прошел через это, и я согласен, что методология не настолько убедительна, поэтому я назвал это «требованием», а не результатом.

РБ

5

И это написано в Microsoft Word: /

гигабайты

0

Функциональные аналоги и ; и были бы интересны в их изучении $P$ $NP$ $FP$ $FNP$ $P$ $=$ вопроса (?). В то время как и являются проблемами решения, которые возвращают битныйответда / нет, и фактически возвращают ответы ( проверяет ответы). Мы знаем, что , если $NP$ $P$ $NP$ $1$ $FP$ $FNP$ $FNP$ $FP$ $=$ $FNP$ $P$ $=$ . $NP$

user3483902
источник

Утверждения, которые подразумевают

Ответы: