Instruções que implicam

22

Essa é uma pergunta em aberto - pela qual peço desculpas antecipadamente.

Existem exemplos de declarações que (aparentemente) não têm nada a ver com complexidade ou máquinas de Turing, mas cuja resposta implicaria ? $\mathbf{P}\neq \mathbf{NP}$

cc.complexity-theory complexity-classes p-vs-np Dominic van der Zypen
fonte

4

"Não existe um sistema de prova para lógica proposicional em que toda tautologia tenha uma prova do comprimento polinomial (no comprimento de )". count, ou isso é muito próximo da complexidade devido ao limite polinomial?

φ

$\varphi$

φ

$\varphi$

Jan Johannsen

Como não há "exatas", responde a minha pergunta, a sua conjectura contaria ... Eu estou apenas procurando surpreender e ângulos diferentes sobre a P vs problema NP

van der Dominic Zypen

4

Eu acho que a complexidade descritiva dá alguns exemplos. Por exemplo, a afirmação "existem propriedades (de estruturas ordenadas) expressáveis por fórmulas existenciais de segunda ordem que não podem ser expressas por fórmulas universais de segunda ordem" é equivalente à resposta de @ JanJohannsen, enquanto "existem propriedades (de estruturas ordenadas) expressáveis por fórmulas existenciais segunda ordem que não podem ser expressas pelos primeiros fórmulas ordem com um operador menos ponto fixo" é precisamente

P \neq N P

$\mathsf P\neq\mathsf{NP}$ . Isso conta?

Damiano Mazza

"

e

". * rimshot *

N \neq 1

$\mathbf{N}\neq 1$

P \neq 0

$\mathbf{P}\neq 0$

David Richerby

1

Pergunta semelhante cstheory.stackexchange.com/questions/9806/…

Tayfun Pay

14

Um sistema de prova para lógica proposicional é chamado polinomialmente delimitado , se toda tautologia tiver uma prova no sistema de comprimento polinomial no comprimento de . $\varphi$ $\varphi$

A declaração "não há polinomialmente delimitada sistema à prova proposicional" é equivalente a por um resultado clássico de Cook e Reckhow , por isso implica . $\mathsf{NP} \neq \mathsf{co}\text-\mathsf{NP}$ $\mathsf{P} \neq \mathsf{NP}$

Jan Johannsen
fonte

2

Gostaria de pensar que (pela definição de um sistema à prova proposicional para o

linguagem -completo de tautologias), a suposição ( "Não existe um sistema de prova para lógica proposicional em que cada tautologia

tem uma prova de polinômio (em o comprimento de

) comprimento ") é quase idêntico ao assumir

; e, consequentemente, quase idêntico ao assumindo

.

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}$

Idd Tzameret

@IddoTzameret: Mas precisamos saber que tautologia é

-completo, certo? E isso não é trivial. Eu acho que este exemplo está apenas reafirmando o interesse de ter problemas completos "naturais": podemos falar sobre classes de complexidade sem falar explicitamente sobre as máquinas usadas para defini-las (o que parece ser o que o OP está pedindo). Ou talvez eu não entendi o seu comentário ...

c o N P

$\mathsf{coNP}$

Damiano Mazza

@ Damiano, acho que o fato de o TAUT ser coNP-completo é trivial, no sentido em que está implícito em sua definição e na integridade do SAT no NP.

Idd Tzameret

@IddoTzameret, Ok, mas você concorda que o

-completeness do SAT não é trivial, certo? Isso é essencialmente o que eu estava dizendo. Quero dizer, entre a afirmação "

" formulada em termos de máquinas de Turing e seu tempo de execução e o estamento "não existe um sistema de prova proposicional polinomialmente limitado" Vejo uma lacuna não trivial, eles definitivamente não ' não parece "quase idêntico". Essa lacuna está na integridade de TAUT ou SAT, o que você quiser, mas está lá. Você não concorda?

N P

$\mathsf{NP}$

N P \neq c o N P

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

Damiano Mazza

1

Sim, a propriedade "

é uma prova de

" deve ser verificável em tempo polinomial (em

e

). E deve ser sólida e completa, ou seja, uma fórmula deve ter uma prova se for uma tautologia.

p

$p$

φ

$\varphi$

| p |

$|p|$

| φ |

$|\varphi|$

Jan Johannsen

12

A teoria da complexidade geométrica (GCT) (também [1]) ainda não foi mencionada. é um grande programa ambicioso para conectar P vs NP à geometria algébrica. por exemplo, uma breve sinopse da pesquisa Entendendo a abordagem de Mulmuley-Sohoni para P vs. NP , Regan:

Estabilidade é informalmente uma noção de não ser “caótico” e se tornou um importante ramo da geometria algébrica sob a influência orientadora de DA Mumford, entre outros. Ketan Mulmuley e Milind Sohoni [MS02] observam que muitas questões sobre classes de complexidade podem ser relançadas como questões sobre a natureza das ações do grupo em certos vetores em determinados espaços que codificam problemas nessas classes. Esta pesquisa explica sua estrutura de um ponto de vista leigo e tenta avaliar se essa abordagem realmente acrescenta novo poder aos ataques à questão P. vs. NP.

também algumas sinopse na seção "Uma nova esperança?" em Status do problema P vs NP , Fortnow (2009)

Mulmuley e Sohoni reduziram uma pergunta sobre a inexistência de algoritmos de tempo polinomial para todos os problemas completos de NP a uma pergunta sobre a existência de um algoritmo de tempo polinomial (com certas propriedades) para um problema específico. Isso deve nos dar alguma esperança, mesmo diante dos problemas (1) - (3).

No entanto, Mulmuley acredita que levará cerca de 100 anos para executar esse programa, se funcionar.

[1] Explicação no estilo Wikipedia da teoria da complexidade geométrica (tcs.se)

vzn
fonte

Obrigado por trazer o GCT! Parece tocar no meu próprio problema [M], mas não o encontrei anteriormente. "Esses problemas computacionais podem ser caracterizados por suas simetrias. O programa visa utilizar essas simetrias para provar limites mais baixos".

DukeZhou 10/0118

10

O resultado a seguir de Raz (Funções Elusivas e Limites Inferiores para Circuitos Aritméticos, STOC'08) tem como objetivo (e não diretamente ), mas pode estar próximo o suficiente para o OP: $VP\neq VNP$ $P\neq NP$

Um polinomial de mapeamento é -elusive, se para cada polinómio de mapeamento de grau , Imagem ( ) imagem ( ). $f:\mathbb F^n \to \mathbb F^m$ $(s, r)$ $Γ : \mathbb F^s → \mathbb F^m$ $r$ $f$ $\not⊂$ $Γ$

Para muitas configurações dos parâmetros , construções explícitas de mapeamentos polinomiais indescritíveis implicam limites inferiores fortes (até exponenciais) para circuitos aritméticos gerais. $n, m, s, r$

Iddo Tzameret
fonte

O que é um mapeamento polinomial? Você quer dizer "polinomial"? Você quer dizer "função computável em tempo polinomial"? Algo mais?

DW

2

É simplesmente uma sequência de

polinômios, cada um com as mesmas

variáveis; portanto, define um mapeamento de

para

.

m

$m$

n

$n$

F^{n}

$\mathbb{F}^n$

F^{m}

$\mathbb{F}^m$

Iddo Tzameret

9

existe um campo de complexidade estudado mais recentemente / chamado complexidade do gráfico, que estuda como os gráficos maiores são construídos a partir de gráficos menores usando operações AND e OR das arestas. Jukna tem uma boa pesquisa . em particular os que utilizam unidades de gráficos "estrela" existe um teorema chave, ver p20 observação 1,18 (o teorema é tecnicamente mais forte do que a seguir e, na verdade, implica ): $P \ne NP/poly$

Já sabíamos (Teorema 1.7) que existem gráficos bipartidos G de complexidade estelar ; de fato, esses são quase todos os gráficos. Por outro lado, o lema da ampliação forte implica que mesmo um limite inferior de para uma constante arbitrariamente pequena na complexidade estelar de um explícito $n × m$ $Star(G) = (nm/ \log n)$ $Star(G) ≥ (2+c)n$ $c > 0$ gráfico com teria grandes conseqüências na complexidade do circuito: esse gráfico daria uma função booleana explícita exigindo circuito detamanhoexponencial (no números de variáveis)! (Lembre-se de que, para funções booleanas, até os limites inferiores super-lineares não são conhecidos até o momento.) Em particular, se o gráfico for tal que a adjacência dos vértices em possa ser determinada por uma máquina de Turing não determinística executando polinômio no tempo em o comprimento binário $n×m$ $G$ $m = o(n)$ $f_G$ $\log_2 nm$ $G$ $G$ dos códigos de vértices, então um limite inferior para uma constante arbitrariamente pequena implica que . Assim, a complexidade estelar dos gráficos captura um dos problemas mais fundamentais da ciência da computação. $log_2 n$ $Star(G) ≥ (2 + c)n$ $c > 0$ $P \ne NP$

vzn
fonte

6

Eu acho que você quer dizer

. A declaração

já trivialmente conhecido.

P / p o l y ⊅ N P

$P/poly \not \supset NP$

P \neq N P / p o l y

$P \neq NP/poly$

Yonatan

@YonatanN

é verdadeiro?

P \neq N P / p o l y

$P\neq NP/poly$

T ....

Sim. Sabe-se que até P / poli contém problemas fora de P, como o problema de parada unária.

Yonatan N

Obrigado pelo link Jukna! "A complexidade é um dos fenômenos científicos cruciais de nossos tempos. Neste capítulo, consideramos a complexidade dos gráficos".

DukeZhou 10/0118

1

Que tal Philip Maymin's

"Os mercados são eficientes se e somente se P = NP " afirmam?

RB
fonte

3

As alegações e "provas" neste artigo não parecem rigorosas, e os argumentos parecem ausentes para mim. Você leu este artigo?

Rahul Savani 11/11

Analisei o assunto e concordo que a metodologia não é tão convincente; foi por isso que a chamei de "afirmação" e não de resultado.

RB

5

E está escrito no Microsoft Word: /

gigabytes

0

$P$ $NP$ $FP$ $FNP$ $P$ $=$ $NP$ $P$ $NP$ $1$ $FP$ $FNP$ $FNP$ $FP$ $=$ $FNP$ $P$ $=$ $NP$

user3483902
fonte

Instruções que implicam

Respostas: