Implicações matemáticas das conjecturas da teoria da complexidade fora do TCS

25

Você conhece conseqüências interessantes de conjecturas (padrão) na teoria da complexidade em outros campos da matemática (isto é, fora da ciência da computação teórica)?

Eu preferiria respostas em que:

  • a conjectura da teoria da complexidade é tão geral e padrão quanto possível; Também estou de acordo com as consequências da dureza de problemas específicos, mas seria bom se os problemas fossem considerados difíceis (ou pelo menos foram estudados em mais de alguns papéis)

  • a implicação é uma afirmação que não se sabe ser verdadeira incondicionalmente ou que outras provas conhecidas são consideravelmente mais difíceis

  • quanto mais surpreendente a conexão, melhor; em particular, a implicação não deve ser uma declaração explícita sobre algoritmos

"Se os porcos pudessem voar, os cavalos cantariam" o tipo de conexões também é bom, desde que os porcos voadores venham da teoria da complexidade e os cavalos cantem de algum campo da matemática fora da ciência da computação.

Esta questão é, em certo sentido, "o inverso" de uma pergunta que tivemos sobre usos surpreendentes da matemática na ciência da computação. Dick Lipton publicou um post exatamente nesse sentido: ele escreve sobre as conseqüências da conjectura de que o fatoração tem grande complexidade de circuitos. As conseqüências são que certas equações diofantinas não têm soluções, um tipo de afirmação que pode ser muito difícil de provar incondicionalmente. A postagem é baseada no trabalho com Dan Boneh, mas não consigo localizar um artigo.

EDIT: Como Josh Grochow observa nos comentários, sua pergunta sobre as aplicações do TCS na matemática clássica está intimamente relacionada. Minha pergunta é, por um lado, mais permissiva, porque não insisto na restrição da "matemática clássica". Penso que a diferença mais importante é que insisto em uma implicação comprovada de uma conjectura de complexidade para uma afirmação em um campo da matemática fora do TCS. A maioria das respostas à pergunta de Josh não é desse tipo, mas fornece técnicas e conceitos úteis na matemática clássica que foram desenvolvidos ou inspirados pelo TCS. No entanto, pelo menos uma resposta à pergunta de Josh é uma resposta perfeita para minha pergunta: o artigo de Michael Freedmanque é motivado por uma pergunta idêntica à minha e prova um teorema da teoria dos nós, condicional em . Ele argumenta que o teorema parece estar fora do alcance das técnicas atuais na teoria dos nós. Pelo teorema de Toda, se então a hierarquia polinomial entra em colapso, portanto a suposição é bastante plausível. Estou interessado em outros resultados semelhantes.P # P = N PP#PNPP#P=NP

Sasho Nikolov
fonte
Relacionados: implicações, não para matemática, mas para "realidade física" #
Austin Buchanan
É o mesmo que cstheory.stackexchange.com/questions/149/… ? Ou essa pergunta pretende ser mais ampla do que aquela?
Joshua Grochow
3
@ Josué, há alguma sobreposição, mas acho que são incomparáveis. Por um lado, não insisto fortemente na matemática "clássica", ou seja, resultados de não complexidade na mecânica quântica estão ok. Por outro lado, gostaria de implicações diretas das conjecturas de CC para os teoremas da matemática fora do TCS, enquanto muitas das respostas para sua pergunta são sobre técnicas desenvolvidas no TCS que nos tornaram úteis na matemática clássica. Ainda assim, cstheory.stackexchange.com/a/163/4896 é uma resposta perfeita para minha pergunta. Sobreposição demais?
Sasho Nikolov
1
Talvez eu devesse ter postado minha resposta à pergunta de Josh aqui: a conjectura em Bürgisser implica resultados em curvas elípticasL .
Bruno
1
@ Sasho: Eu acho que está tudo bem. Agradeço por ter esclarecido. (BTW, quando eu disse "clássica" em minha outra pergunta, não pretendia excluir a mecânica quântica - na verdade, a teoria quântica de campos e a álgebra quântica são os principais tópicos matemáticos da atualidade, estudados em um grande número de departamentos de matemática (mesmo os melhores) .)
Joshua Grochow

Respostas:

14

Aqui está outro exemplo da teoria dos grafos. O teorema menor do gráfico nos diz que, para cada classe de gráficos não direcionados que são fechados em menores de idade, existe um conjunto de obstruções finitas modo que um gráfico está em se e somente se ele não contiver um gráfico em como menor de idade. No entanto, o teorema menor do gráfico é inerentemente não construtivo e não nos diz nada sobre o tamanho desses conjuntos de obstruções, ou seja, quantos gráficos ele contém para uma escolha específica de .O b s ( G )GObs(G)O b s ( L ) LGObs(G)G

Em Muitas Obstruções de Ordem Menor , Michael J. Dinneen mostrou que sob uma conjectura teórica da complexidade plausível, os tamanhos de vários desses conjuntos de obstruções podem ser grandes. Por exemplo, considere a classe parametrizada de gráficos do gênero no máximo . À medida que aumenta, podemos esperar que os conjuntos de obstruções se tornem cada vez mais complicados, mas quanto? Dinneen mostrou que, se a hierarquia polinomial não cair para o terceiro nível, não haverá polinômio tal que o número de obstruções em seja delimitado por kk O b s ( L k )p ó b s ( L k )p(k) O b s ( L 0 )={ K 5 , K 3 , 3 } L K KL L kGkkkObs(Gk)pObs(Gk)p(k). Como o número de obstruções menores por ter o gênero zero (ou seja, ser plano) é apenas dois ( ), esse crescimento superpolinomial não é imediatamente óbvio (embora eu acredite que possa ser provado incondicionalmente). O bom do resultado de Dinneen é que ele se aplica aos tamanhos dos conjuntos de obstruções correspondentes a qualquer conjunto parametrizado de ideais menores para os quais decidir o menor para o qual é NP- Difícil; em todos esses ideais menores parametrizados, os tamanhos dos conjuntos de obstruções devem crescer superpolinomialmente. Obs(G0)={K5,K3,3}GkkGGk

Bart Jansen
fonte
Obrigado Bart! Isto é muito interessante. Estou aceitando sua resposta como a mais votada. Obrigado a todos pelas respostas!
Sasho Nikolov
6

Aqui está um exemplo: A complexidade computacional e a assimetria informacional em produtos financeiros de Arora, Barak e Ge mostram que pode ser computacionalmente intratável (por exemplo, NP-hard) para precificar corretamente os derivativos - eles usam o subgráfico mais denso como um problema rígido incorporado.

Na mesma linha e muito antes, está o famoso artigo de Bartholdi, Tovey e Trick sobre a dureza de manipular uma eleição.

Suresh Venkat
fonte
2
Suresh, até certo ponto, esses ainda são resultados de complexidade (com implicações sociais). Eu tinha em mente resultados que não são sobre algoritmos. Ainda assim, ambos são ótimos!
Sasho Nikolov
Eu não tinha certeza do que você estava procurando. Suponho que você queira algo como o inverso de "curvas fechadas semelhantes ao tempo colapsam o quantum e o clássico"?
Suresh Venkat
1
Na verdade, o resultado da CTC é um exemplo perfeito. Quero dizer, nem mesmo o inverso, mas a afirmação em contrapositiva: se o quântico e o clássico não entrarem em colapso, os CTCs (polinomiais) não existirão.
Sasho Nikolov
1
então você está dizendo que eu deveria postar uma nova resposta :)?
precisa saber é o seguinte
Eu acho que eu estou dizendo que :)
Sasho Nikolov
5

Você pode usar conjecturas teóricas da complexidade para provar coisas sobre, por exemplo, a teoria da representação do grupo simétrico (consulte esta postagem no blog ). Grosso modo, uma vez que o problema de palavras do grupo simétrico é difícil de coNP, não pode ter uma representação fiel (ou seja, injetiva) de dimensão menor que menos que O SAT possui circuitos de tamanho subexponencial. S 2 k 2 δ kS2kS2k2δk

Está muito no espírito do artigo de Mike Freedman mencionado anteriormente.

Izaak Meckler
fonte
-6

parece que muitas questões de separação de classes de complexidade do TCS têm implicações importantes em matemática. a questão P =? NP em particular parece ter conexões muito profundas em muitos campos e isso inclui a matemática. alguns casos notáveis ​​nesta área:

  • Foi demonstrado que o problema de Hilberts Nullstellensatz formulado no início do século XX tem uma tratabilidade intimamente relacionada à complexidade P vs NP, por exemplo, SOBRE A INTRACTABILIDADE DE NULLSTELLENSATZ DE HILBERT E UMA VERSÃO ARGÉNICA DE “NP ̸ = P?” Por Shub / Smale. esta é uma área de estudo contínua, por exemplo, em Álgebra, Combinatória e Complexidade: Problemas de Hilbert Nullstellensatz e NP-complete by Margulies.

  • Teorema de Fagins (wikipedia):

    O teorema de Fagin é um resultado da teoria descritiva da complexidade que afirma que o conjunto de todas as propriedades expressáveis ​​na lógica existencial de segunda ordem é precisamente a classe de complexidade NP. É notável, pois é uma caracterização da classe NP que não invoca um modelo de computação como uma máquina de Turing.

    a principal / surpreendente implicação de P = NP aqui significaria que todas as asserções lógicas de segunda ordem poderiam ser computadas com eficiência.

  • outro caso é que existem vários problemas completos de NP declarados principalmente apenas em termos matemáticos (por exemplo, nenhuma referência a conceitos de TCS como TMs, não determinismo etc.). essa lista pode ser muito grande se a teoria dos grafos for (razoavelmente) considerada matemática. no entanto, mesmo interpretações restritas de "matemáticas" levam a casos, por exemplo, na teoria dos números.

    Como provado por Manders e Adleman , o seguinte problema é NP-completo: dados os números naturais , determinam se existe um número natural tal que .x c x 2aa,b,cxcx2a(modb)

vzn
fonte
3
você não entendeu a pergunta: todos os resultados mencionados são sobre complexidade. eu quero uma conseqüência não-complexidade do aa declaração em teoria da complexidade
Sasho Nikolov