Principais problemas não resolvidos em ciência da computação teórica?

218

A Wikipedia lista apenas dois problemas em "problemas não resolvidos em ciência da computação" :

Quais são outros problemas importantes que devem ser adicionados a esta lista?

Regras:

  1. Apenas um problema por resposta
  2. Forneça uma breve descrição e todos os links relevantes
Shane
fonte
11
Como você está solicitando uma lista e não há uma resposta única, isso pode funcionar melhor como um wiki da comunidade.
Daniel Apon
2
Um problema não resolvido por resposta, por favor; então podemos facilmente classificar as respostas votando para cima / para baixo!
Jukka Suomela 17/08/10
15
Por que apenas resultados de complexidade? O TCS tem mais do que complexidade! Não há problemas em aberto na teoria dos tipos? linguagens de programação?
Jacques Carette
3
adicione-os, Jacques :).
Suresh Venkat
8
Acho que devemos distinguir entre os principais problemas abertos que são vistos como problemas fundamentais , como , e os principais problemas abertos que constituirão um avanço técnico, se resolvidos, mas que não sejam necessariamente tão fundamentais, por exemplo, limites exponenciais inferiores em A C 0 ( 6 ) circuitos (isto é, portas). Portanto, devemos abrir um novo wiki da comunidade intitulado "problemas abertos nas fronteiras do TCS" ou algo semelhante. PNPAC0(6)AC0+mod6
Iddo Tzameret

Respostas:

137

A multiplicação de por matrizes pode ser feita em operações ?n O ( n 2 )nnO(n2)

O expoente do limite superior mais conhecido ainda possui um símbolo especial, . Atualmente é de aproximadamente 2.376, pelo algoritmo Coppersmith-Winograd . Uma boa visão geral do estado da arte é Sara Robinson, Em direção a um algoritmo ideal para multiplicação de matrizes , SIAM News, 38 (9), 2005.ωωω

Atualização: Andrew Stothers (em sua tese de 2010 ) mostrou que , que foi aprimorado por Virginia Vassilevska Williams (em uma pré-impressão em julho de 2014 ) para . Esses limites foram obtidos por uma análise cuidadosa da técnica básica de Coppersmith-Winograd.ω < 2,372873ω<2.3737ω<2.372873

Atualização adicional (30 de janeiro de 2014): François Le Gall provou que em um artigo publicado no ISSAC 2014 ( pré-impressão arXiv ).ω<2.3728639

András Salamon
fonte
Como cerca de um objetivo modesto e realista de ou alguma outra função entre n 2 + ε e n 2 ? Afinal, espera-se que a multiplicação inteira tenha o limite inferior de O ( n log n ) . O(n2logn)n2+ϵn2O(nlogn)
Mitch
Não tenho certeza de que ir de a 2 + ϵ seja considerado um "objetivo modesto e realista", e muito menos ficar abaixo de 2 + ϵ . Mas seria ótimo ver algum progresso, então tente! 2+0.3762+ϵ2+ϵ
András Salamon
13
O expoente de multiplicação da matriz é definido como o menor número real modo que O ( n ω + ϵ ) operações aritméticas são suficientes para todos ϵ > 0 . Provavelmente, um fator como log n deve ser esperado. ωO(nω+ϵ)ϵ>0logn
Zeyu 13/11/2010
2
Apenas acrescentando, por uma questão de exaustividade, o conhecimento atual de que a CW bound foi melhorada alguns dias atrás por Virginia Williams. E como observado por muitos outros na comunidade, Andrew Stothers havia conseguido derrotar a CW cerca de um ano antes da Virgínia. O registro atual é O(n2.373)
Akash Kumar 08/12
123

O isomorfismo do gráfico está em P?

A complexidade do isomorfismo de grafos (IG) é uma questão em aberto há várias décadas. Stephen Cook mencionou isso em seu artigo de 1971 sobre a NP-completude do SAT .

Determinar se dois gráficos são isomórficos geralmente pode ser feito rapidamente, por exemplo, por software como nautye saucy. Por outro lado, Miyazaki construiu classes de instâncias para as quais, nautycomprovadamente, requer tempo exponencial.

Read e Corneil revisaram as muitas tentativas de lidar com a complexidade do IG até aquele momento: The Graph Isomorphism Disease , Journal of Graph Theory 1 , 339-363, 1977.

Não se sabe que GI está em co-NP, mas existe um protocolo aleatório simples para Non-Isomorphism de Gráfico (RNB). Portanto, acredita-se que GI (= co-RNB) esteja "próximo a" NP co-NP.

Por outro lado, se GI estiver NP-completa, a Hierarquia Polinomial entrará em colapso. Portanto, é improvável que o GI seja NP-completo. (Boppana, Håstad, Zachos, co-NP tem provas interativas curtas?, IPL 25 , 127–132, 1987)

Shiva Kintali tem uma boa discussão sobre a complexidade do IG em seu blog.

Laszlo Babai provou que o isomorfismo do gráfico está no tempo subexponencial .

András Salamon
fonte
Por favor, dê uma olhada nesta entrada também.
MS Dousti
Ativei um limite inferior exato para a detecção genérica de automorfismo de força bruta. oeis.org/A186202 Muito menos que mas ainda exponencial. Esperando que McKay acoplará aos Schrier-Sims sua última encarnação do NAUTY para fazê-lo rodar em hardware paralelo. n!
Chad Brewbaker
11
Babai retirou a alegação de tempo de execução quase-polinomial . Aparentemente, houve um erro na análise.
Raphael
4
A alegação foi restaurado: people.cs.uchicago.edu/~laci/update.html
niting
91

Complexidade da Factoring

Factoring está em ?P

Kaveh
fonte
Alguma boa publicação que você conhece descreve a complexidade do fatoramento ou do teste de primalidade em termos da estrutura do semigrupo de transformações de adição e multiplicação em Z_n? Por exemplo, em [0,1,2] é a 0 | transformar x1, [1,2,0] é o +1 transformar ...Z3
Chad Brewbaker
72

P = BPP?

Diego de Estrada
fonte
2
Essa resposta deve ser feita CW agora também ...
Shane
2
e questões relacionadas, como é NP = MA = AM?
Robin Kothari
11
Veja a questão intimamente relacionada cstheory.stackexchange.com/questions/64/…
András Salamon
66

Existe uma regra de giro para o algoritmo simplex que produz o pior tempo de execução polinomial? De maneira mais geral, existe algum algoritmo fortemente polinomial para programação linear?

Jɛ ff E
fonte
11
Acrescentarei a esta pergunta: mostrar a inexistência de LP fortemente polinomial implicaria algum resultado de separação de classe?
Anand Kulkarni
,,, e a conjectura de Hirsch ...
Sariel Har-Peled
7
Em 2011, Oliver Friedmann mostrou limites exponenciais inferiores para muitas regras de giro (ele na verdade alega regras de giro "essencialmente todas naturais", incluindo Random Facet e Random Edge). Esses limites se aplicam ao resolver um programa linear derivado de jogos de paridade para 2 jogadores. A tese de Friedmann edoc.ub.uni-muenchen.de/13294 examina a história em profundidade (incluindo várias formas da conjectura de Hirsch e o contra-exemplo de 2010 à forma forte de Francisco Santos).
András Salamon
63

A hipótese de tempo exponencial (ETH) afirma que resolver SAT requer tempo exponencial de 2 Ω (n) . ETH implica muitas coisas, por exemplo, que SAT não está em P, então ETH implica P ≠ NP. Veja Impagliazzo, Paturi, Zane, que problemas têm complexidade fortemente exponencial? , JCSS 63, 512-530, 2001.

Acredita-se amplamente que o ETH, mas provavelmente seja difícil de provar, pois implica muitas outras separações de classes de complexidade.

András Salamon
fonte
4
Sério, eu não chamaria o ETH de um grande problema em aberto neste momento exatamente porque implica P ≠ NP e, portanto, é pelo menos tão difícil de provar.
Holger
17
Não? IMHO, seu argumento implica que o ETH é ainda mais um grande problema em aberto do que o PvsNP.
Jeffε
Você poderia explicar por que não implica o ETH? PNP
Emil
13
Se , então P N P , mas ETH é falso. NP=PTIME(nlogn)PNP
Jeffε 31/08/10
3
Ah ok. Mas você quer dizer DTIME ( )? nlogn
Emil
59

Immerman e Vardi mostram que a lógica de ponto fixo captura PTIME na classe de estruturas ordenadas . Um dos maiores problemas em aberto na teoria descritiva da complexidade é se a dependência da ordem pode ser removida:

Existe uma lógica que captura PTIME?

Simplificando, uma lógica de captura de PTIME é uma linguagem de programação para problemas de gráfico que funciona diretamente na estrutura do gráfico e não tem acesso à codificação dos vértices e arestas, de forma que o seguinte seja válido:

  1. qualquer programa sintaticamente correto modela um problema de gráfico computável em tempo polinomial e
  2. qualquer problema de gráfico computável em tempo polinomial pode ser modelado por um programa sintaticamente correto.

Se não houver lógica que capture PTIME, pois NP é capturado pela lógica existencial de segunda ordem. Uma lógica que captura o PTIME forneceria um possível ataque ao P vs NP.PNP

Veja o blog de Lipton para uma discussão informal e M. Grohe: A busca por uma captura de lógica PTIME (LICS 2008) para uma pesquisa mais técnica.

Holger
fonte
3
Immerman-Vardi mostra que a FO (LFP) captura a lógica em estruturas <i> ordenadas </i>, então essa é uma pergunta sobre a captura de PTIME em modelos finitos arbitrários. Se eu entendi direito, essa pergunta não é uma tradução de perguntar se P! = NP? Pode ser mais interessante perguntar a um ou mais dos problemas em aberto na pesquisa à qual você vincula. Desculpas se estou sendo ignorante aqui.
Aaron Sterling
5
Obrigado, editei a resposta para mencionar a Immerman-Vardi para esclarecimentos. Não, esse problema em aberto não é conhecido por ser equivalente a P vs NP. Os problemas em aberto na pesquisa são casos especiais do grande problema em aberto e não são apropriados neste segmento. Talvez essa referência também seja útil: rjlipton.wordpress.com/2010/04/05/…
Holger
55

A conjetura de jogos únicos é verdadeira?
E: considerando que existem algoritmos de aproximação de tempo subexponencial para jogos exclusivos , onde o problema está em termos de cenário de complexidade?

Anand Kulkarni
fonte
Não seria mais preciso dizer que, se o UGC não é verdadeiro (ou seja, jogos únicos não são difíceis de NP, apenas mais difíceis que P), onde o UGC se encaixaria na paisagem?
András Salamon
Opa Sim, eu deveria reformular isso. Minha intenção era destacar a aparente discrepância resultante de jogos únicos com um algoritmo de aproximação não trivial em tempo subexponencial (mas não totalmente polinomial). Mais sobre: ​​O que isso diz, se o tempo de execução subexponencial for ideal para jogos exclusivos?
Daniel Apon 17/08/10
2
Em retrospecto, pensei em incluir um ponteiro para esta pré-impressão . Na minha opinião, é um desenvolvimento tão grande quanto o artigo que vinculei na resposta.
Daniel Apon 31/08/10
11
Vale ressaltar que não existem instâncias conhecidas do UCG. A melhor abordagem atual funciona eficientemente em todos os casos testados. Simplesmente não podemos provar que encontramos os exemplos mais patológicos.
Stella Biderman
55

Permanente versus Determinante

A questão permanente versus determinante é interessante por causa de dois fatos. Primeiro, a permanente de uma matriz conta o número de combinações perfeitas em um gráfico bipartido. Portanto, a permanente dessa matriz é # P-Complete. Ao mesmo tempo, a definição de permanente é muito próxima à do determinante, em última análise diferente apenas por causa de uma simples mudança de sinal. Sabe-se que os cálculos determinantes estão em P. O estudo das diferenças entre o permanente e o determinante e quantos cálculos determinantes são necessários para calcular o permanente falam sobre P versus #P.

Kaveh
fonte
5
Para mim, isso não se qualifica como um "grande problema em aberto", porque a questão teórica da complexidade real (eles têm complexidades diferentes) é subsumida por P = NP (já que #P é um superconjunto de NP) e com essa pergunta deixada de lado não há um problema concreto colocado aqui.
David Eppstein
Na verdade, eu concordo com isso.
Ross Snider
10
@ David David Eppstein: Per v. Det está mais próximo de GapP v GapL, um análogo de contagem de NP v NL. É possível que e, portanto, L um p P L um p L . Além disso, per v det é muito mais antigo que P v NP, basicamente voltando a [Polya 1913], no qual ele mostra que não se pode afixar sinais em uma matriz para mudar sua permanente para sua determinante (exceto 2x2). A Valiant introduziu uma variante nessas perguntas (permitindo que o tamanho de det seja maior que n) devido à sua importância na complexidade, mas mesmo os trabalhos pré-Valiant dão a motivação "porque a permanente é tão difícil de calcular ..." (por exemplo, Gibson 1971)NLP=NPGapPGapL
Joshua Grochow
Quais são os algoritmos de última geração para o cálculo da permanente de uma matriz 0-1? ou seja, o número de matrizes de permutação legal que você pode gerar a partir de um subconjunto dos 1s.
Chad Brewbaker
@ChadBrewbaker: veja Mark Jerrum, Alistair Sinclair, Eric Vigoda, "Um algoritmo de aproximação de tempo polinomial para a permanente de uma matriz com entradas não negativas", Journal of the ACM 51/4 (2004), 671, citeseerx.ist. psu.edu/viewdoc/summary?doi=10.1.1.141.116
Zsbán Ambrus
47

Podemos calcular a FFT em muito menos do que tempo?O(nlogn)

Nas mesmas (muito) veia geral, há muitas perguntas de melhorar os tempos de execução dos diversos problemas clássicos ou algoritmos: por exemplo, podem todos os pares de-menores-caminhos (APSP) ser resolvidos em hora ?O(n3ϵ)

Editar: o APSP é executado no tempo "onde adições e comparações de reais são custo unitário (mas todas as outras operações têm custo típico logarítmica)":http://arxiv.org/pdf/1312.6680v2.pdf(n32Ω(logn)1/2)

Alex Andoni
fonte
3
Um desenvolvimento interessante na FFT: "* Um algoritmo de tempo O (k log n) para o caso em que o sinal de entrada tem no máximo k coeficientes de Fourier diferentes de zero e * Um O (k log n log (n / k)) algoritmo de tempo para sinais gerais de entrada ". fonte: arxiv.org/abs/1201.2501v1
Shadok
45

Um algoritmo determinístico de tempo linear para o problema mínimo de extensão .

Suresh Venkat
fonte
44

NP versus co-NP

A questão NP versus co-NP é interessante porque NP ≠ co-NP implica P ≠ NP (como P é fechado no complemento). Também se refere à "dualidade": separação entre encontrar / verificar exemplos e encontrar / verificar contra-exemplos. De fato, provar que uma pergunta está em NP e co-NP é nossa primeira boa evidência de que um problema que parece estar fora de P também provavelmente não é NP-Complete.

Ross Snider
fonte
7
Isso também está relacionado à complexidade da prova proposicional. Existe um sistema de prova proposicional polinomial se for igual a c o N PNPcoNP .
Kaveh
41

Existem problemas que não podem ser resolvidos com eficiência por computadores paralelos?

Problemas com P-completo não são conhecidos por serem paralelizáveis. Os problemas de P-completo incluem Horn-SAT e Programação Linear. Mas provar que esse é o caso exigiria a separação de uma noção de problemas paralelizáveis ​​(como NC ou LOGCFL) de P.

Os projetos de processadores de computador estão aumentando o número de unidades de processamento, na esperança de que isso traga um desempenho aprimorado. Se algoritmos fundamentais, como a Programação Linear, não são inerentemente paralelizáveis, há consequências significativas.

András Salamon
fonte
16
Tenho certeza de que os algoritmos de LP, como estão hoje, não são paralelizáveis. Eu acredito que eles se encaixam no modelo de operações de RAM sem bit de Mulmuley. Em dx.doi.org/10.1137/S0097539794282930 K. Mulmuley . Limites inferiores em um modelo paralelo sem operações de bit. SIAM J. Comput. 28 (4), 1460-1509 (1999), mostra que nesse modelo, mostrando que muitos algoritmos naturais (geralmente numéricos) para problemas completos de P não são paralelizáveis. Isso não responde à pergunta no caso booleano, mas responde a uma grande classe de algoritmos naturais. PNCP
Joshua Grochow
41

Todas as tautologias proposicionais têm provas de Frege de tamanho polinomial?

Indiscutivelmente o principal problema aberto da complexidade da prova : demonstrar limites inferiores do tamanho super-polinomial nas provas proposicionais (também chamadas de provas de Frege).

Informalmente, um sistema de prova de Frege é apenas um sistema de prova proposicional padrão para provar tautologias proposicionais (se aprende em um curso de lógica básica), tendo axiomas e regras de dedução, onde as linhas de prova são escritas como fórmulas. O tamanho de uma prova de Frege é o número de símbolos necessários para anotar a prova.

O problema então pergunta se existe uma família (Fn)n=1 de fórmulas tautológicas proposicionais para as quais não há p polinomial tal que o tamanho mínimo à prova de Frege de Fn seja no máximo p(|Fn|) , por tudo n=1,2, (onde |Fn| indica o tamanho da fórmula Fn ).


Definição formal de um sistema à prova de Frege

Definição (regra de Frege) Uma regra de Frege é uma sequência de fórmulas proposicionais A0(x¯),,Ak(x¯) , para k0 , escrito como A1(x¯),,Ak(x¯)A0(x¯) . No caso dek=0, a regra de Frege é chamada deesquema de axioma. Diz-se queuma fórmulaF0éderivada pela regradeF1,,FkseF0,,Fksão todas instâncias de substituição deA1,,Ak, para alguma atribuição àsvariáveisx¯( isto é, existem fórmulas B1,,Bn tal queFi=Ai(B1/x1,,Bn/xn), para todos osi=0,,k . Diz-se que aregra de Frege ésólidase, sempre que uma atribuição satisfizer as fórmulas no lado superior A1,,Ak , também satisfaz a fórmula no lado inferiorA0 .

Definição (prova de Frege) Dado um conjunto de regras de Frege, uma prova de Frege é uma sequência de fórmulas de modo que cada linha de prova é um axioma ou foi derivada por uma das regras de Frege fornecidas a partir de linhas de prova anteriores. Se a sequência termina com a fórmula A , em seguida, a prova é dito ser um comprovante de A . O tamanho de uma prova de Frege é o tamanho total de todas as fórmulas da prova.

Um sistema de prova é dito ser implicationally completa se para todos conjunto de fórmulas T , se T semanticamente implica F , então existe uma prova de F utilizando (possivelmente) axiomas de T . Diz-se que um sistema de prova é bom se admitir provas de apenas tautologias (quando não estiver usando axiomas auxiliares, como no T acima).

Definição (sistema à prova de Frege) Dada uma linguagem proposicional e um conjunto finito P de regras sonoras de Frege, dizemos que P é um sistema à prova de Frege se P é implicationally completa.

Observe que uma prova de Frege é sempre válida, pois as regras de Frege são consideradas válidas. Não precisamos trabalhar com um sistema específico de prova de Frege, pois um resultado básico na complexidade da prova afirma que todos os dois sistemas de prova de Frege, mesmo em idiomas diferentes, são polinomialmente equivalentes [Reckhow, tese de doutorado, Universidade de Toronto, 1976].


Estabelecimento de limites inferiores em provas Frege poderia ser visto como um passo para provar NPcoNP , uma vez que se isto for verdadeira, então nenhum sistema prova proposicional (incluindo Frege) pode ter provas tamanho polinomiais para todos os tautologia.

Iddo Tzameret
fonte
38

Podemos calcular a distância de edição entre duas cadeias de comprimento no tempo sub-quadrático, ou seja, no tempo O ( n 2 - ϵ ) para alguns ϵ > 0 ?nO(n2ϵ)ϵ>0

Piotr
fonte
8
Você tem referências para isso? Na verdade, eu pensei que essa proposição era trivialmente falsa, embora eu não consiga pensar em uma prova do topo da minha cabeça. (Embora eu estou ciente de que o tempo de execução pode ser feita dependente do número de erros.)
Konrad Rudolph
5
Atualização (STOC 2015): Backurs e Indyk fornecem evidências de que o tempo melhor que o quadrático não é possível. Consulte rjlipton.wordpress.com/2015/06/01/puzzling-evidence .
Neal Young
38

Existem algoritmos de tempo verdadeiramente subquadrático (significando tempo para alguma constante δ > 0 ) para problemas difíceis de 3SUM ?O(n2δ)δ>0

Em 2014, Grønlund e Pettie descrito um algoritmo determinista por si 3SUM que é executado no tempo . Embora este seja um resultado importante, a melhoria em relação ao O ( n 2 ) é apenas (sub) logarítmica. Além disso, nenhum algoritmo subquadrático semelhante é conhecido para a maioria dos outros problemas difíceis do 3SUM.O(n2/(logn/loglogn)2/3)O(n2)

Aryabhata
fonte
9
Boa pergunta. No entanto, a existência de algoritmos sub-quadráticos para o problema 3SUM está aberta, mesmo para algoritmos aleatórios . Claro, algoritmo determinista teria sido ainda melhor ..
Piotr
3
No caso quântico, são conhecidos os limites inferiores e superiores correspondentes de n log (n) para o 3SUM: Andrej Dubrovsky, Oksana Scegulnaja-Dubrovska Limites Quânticos Aprimorados para o Problema de 3-Soma. Proceedings of Baltic DB&IS 2004, vol. 2, Riga, Letônia, pp. 40-45.
Martin Schwarz
11
Fiquei com a impressão de que não temos n ^ 2 limite inferior para qualquer problema no NP.
Sariel Har-Peled
11
Tive a impressão distinta de que, se você estiver restrito a problemas de decisão (sem argumentos de saída), nada será conhecido. Mas você realmente deve perguntar a uma pessoa complexa.
Sariel Har-Peled
3
Um artigo recente do arXiv afirma ter resolvido essa conjectura fornecendo algoritmos sub-quadráticos para o 3-SUM.
Mangara 7/07/2014
35

BQP = P?

Também: NP contido no BQP?

Eu sei que isso violou as regras ao ter duas perguntas na resposta, mas quando feitas com a pergunta P vs NP, elas não são necessariamente perguntas independentes.

Joe Fitzsimons
fonte
33
  1. Conjectura de Isomorfismo. (Todos os problemas de NP-completos são o "mesmo" problema?)
  2. A criptografia pode ser baseada em um problema NP-completo?

  3. e, um pouco mais longe do mainstream:

  4. Qual é o tamanho do NP no EXP?

(Informalmente, se você tem todos os problemas no EXP em uma tabela e escolhe um uniformemente aleatoriamente, qual é a probabilidade de o problema escolhido também estar no NP? Esta questão foi formalizada pela noção de medida limitada a recursos Sabe-se que P mede zero dentro de EXP, ou seja, o problema que você pegou da tabela quase certamente não está em P.)

Aaron Sterling
fonte
É o mesmo que p-measure no zoológico de Complexidade? Onde eu iria ler mais sobre isso?
András Salamon
2
A medida P é um exemplo de medida limitada a recursos: de maneira mais geral, você pode imaginar uma máquina tentando prever uma sequência, e os recursos computacionais disponíveis para isso são os que fornecem o recurso vinculado à medida. Eu usei p-measure em minha explicação informal de EXP em uma tabela. Para uma leitura mais aprofundada, recomendo a versão em diário da seguinte pesquisa de Lutz (a CZ cita a versão em conferência desta pesquisa). cs.iastate.edu/~lutz/=PAPERS/qset.ps (em PostScript, espero que isso é ok)
Aaron Sterling
Obrigado. Aqui está um PDF desse artigo para aqueles que não sabem ler PS: archives.cs.iastate.edu/documents/disk0/00/00/01/28/00000128-01/…
András Salamon
2
Sim para sua primeira pergunta. P tem a medida 0 em EXP; portanto, se NP não, você obtém P! = NP imediatamente. Para a segunda pergunta, sugiro que você leia o último parágrafo da página 28 na pesquisa a que Andras e eu vinculamos. (Não há espaço suficiente no comentário para colá-lo aqui, desculpe.) Basicamente, se o NP medir zero, existe um algoritmo viável que poderia adivinhar a participação em um problema difícil do NP "de maneira irracional". Portanto, parece provável que NP não seja a medida zero dentro de EXP.
Aaron Sterling
11
@Artem: você pode começar por aqui: blog.computationalcomplexity.org/2003/03/…
Aaron Sterling
29

Qual é a aproximabilidade do Metric TSP ? O algoritmo de Christofides de 1975 é um algoritmo de aproximação em tempo polinomial (3/2). É NP-difícil fazer melhor?

  • Aproximar o TSP métrico para um fator menor que 220/219 é NP-difícil (Papadimitriou e Vempala, 2006 [PS] ). Que eu saiba, esse é o limite inferior mais conhecido.

  • Há alguma evidência sugerindo que o limite real pode ser 4/3 (Carr e Vempala, 2004 [versão gratuita] [boa versão] ).

  • 13/9

James King
fonte
11
TSP métrico feito recentemente por 3/2 - e onde e é constante (próximo a 0,002)
Saeed
11
alguma discussão sobre TSP métrica em carta perdida de Godel
Artem Kaznatcheev
2
@Saeed, você quis dizer o algoritmo apenas para o caso especial do Metric TSP: para Graphic TSP? Então foi melhorado para 13/9 por Mucha. Parece que 3/2 é o limite superior mais conhecido para o Metric TSP.
Alex Golovnev
@AlexGolovnev, Oi Alex, Sim, mas meu comentário foi antes da chegada do novo artigo;) (eu vi o jornal Oveis Gharan na época).
Saeed
28

Atribua uma função explícita com complexidade de circuito exponencial.

Shannon provou em 1949 que se você escolher uma função booleana aleatoriamente, ela tem complexidade de circuito exponencial com probabilidade quase uma.

f:{0,1}n{0,1}5n-o(n)

Kaveh
fonte
11
Essa maneira de expressar o problema sempre me incomoda, porque você precisa ter cuidado com o que quer dizer com "explícito". É fácil escrever uma descrição de uma função que tem complexidade de circuito exponencial. Se "explícito" significa "computável em tempo exponencial ou menos", então eu concordo, este é um grande problema em aberto.
Ryan Williams
11
Ryan, você está certo. Este é um ponto extremamente importante. Também é fácil escrever uma descrição de uma função não confiável. No artigo que cito, o limite inferior é provado para uma função que é construtível no tempo polinomial determinístico.
Marc
Existe uma boa exposição sobre o trabalho de Shannon?
T ....
3
O argumento é detalhado nas seguintes notas de aula: math.tau.ac.il/~zwick/scribe-boolean.html
Marc
Este é um excelente problema e traz de volta boas lembranças de ter recebido o resultado de Shanon no meu segundo ano de universidade.
Stella Biderman
27

ϵ1/ϵ1/ϵ

arnab
fonte
27

Separe o NEXP do BPP. As pessoas tendem a acreditar em BPP = P, mas ninguém pode separar o NEXP do BPP.

Bin Fu
fonte
26

Sei que o OP pediu apenas um problema por postagem, mas as conferências RTA (Técnicas de Reescrita e seus Aplicativos) 1 e TLCA (Typed Lambda Calculi e seus Aplicativos) mantêm listas de problemas em aberto em seus campos 2 . Essas listas são bastante úteis, pois também incluem indicadores para o trabalho anterior feito na tentativa de resolver esses problemas.

Dominic Mulligan
fonte
11
Sem problemas. Alguém conhece outras listas semelhantes de outras conferências? Eles são bem interessantes de ler.
Dominic Mulligan
26

Derandomização do problema do Teste de Identidade Polinomial

PP identicamente zero?

Esse problema pode ser resolvido em tempo polinomial aleatório, mas não é conhecido por ser solucionável em tempo polinomial determinístico.

τPττ(P)P1PZ[x]z(P)

cPZ[x]z(P)(1+τ(P))c

Bruno
fonte
25

Existe um teorema do Quantum PCP?

Robin Kothari
fonte
Esta questão foi mencionada no blog de Scott Aaronson há um tempo atrás, scottaaronson.com/blog/?p=139, mas não sei se houve algum progresso desde então.
Anthony Leverrier
Eu acho que essa resposta precisa ser atualizada.
precisa
@ Kaveh: O que você gostaria de ver adicionado?
precisa
25

Existem muitos problemas em aberto no cálculo lambda (digitado e não digitado). Veja a lista de problemas em aberto da TLCA para obter detalhes; há também uma boa versão em PDF sem os quadros.

Eu particularmente gosto do problema # 5:

Fω

Jacques Carette
fonte
3
Agradeço a Dominic Mulligan por me indicar essa lista específica de problemas.
Jacques Carette
25

O problema do logaritmo discreto está em P?

Gqg,hGgGnNgn=hq

gabg,gagbg,ga,gb,hGgab=h

Claramente, o DLP é difícil se CDH é difícil e CDH é difícil se DDH é difícil, mas nenhuma redução inversa é conhecida, exceto em alguns grupos. A suposição de que o DDH é difícil é essencial para a segurança de alguns sistemas de criptografia, como ElGamal e Cramer-Shoup .

Felipe Lacerda
fonte
3
Bem, sabemos que o DLP está contido no BQP.
Joe Fitzsimons
DLP foi recentemente colocado em quase-P para o grupoG=Fpn×
Mark
24

Jogos de paridade são jogos gráficos de duração infinita para dois jogadores, cujo problema de decisão natural está em NP e co-NP e cujo problema de pesquisa natural em PPAD e PLS.

http://en.wikipedia.org/wiki/Parity_game

Os jogos de paridade podem ser resolvidos em tempo polinomial?

(De maneira mais geral, uma grande questão em aberto em programação matemática é se os problemas de complementaridade linear da matriz P podem ser resolvidos em tempo polinomial?)

Rahul Savani
fonte
23

A área de complexidade parametrizada possui sua própria carga de problemas em aberto.

Considere os problemas de decisão

  • dado (G,k) existe uma cobertura de tamanho de vértice k para o gráfico G?
  • dado (F,k) existe uma atribuição satisfatória de peso k para a fórmula F?
  • dado (G,k) existe uma camarilha de tamanho k em um gráfico G?
  • etc ...

Muitos, MUITOS, problemas combinatórios existem nesta forma. A complexidade parametrizada considera que um algoritmo é "eficiente" se seu tempo de execução for superior ao limite def(k)nc Onde f é uma função arbitrária e cé uma constante independente dek. Em comparação, observe que todos esses problemas podem ser facilmente resolvidos emnO(k).

Essa estrutura modela os casos em que estamos procurando uma pequena estrutura combinatória e podemos oferecer tempo de execução exponencial em relação ao tamanho da solução / testemunha .

Um problema com esse algoritmo (por exemplo, cobertura de vértices) é chamado de FPT ( Fixed Parameter Tractable ).

A complexidade parametrizada é uma teoria madura e possui fortes fundamentos teóricos e apela a aplicações práticas. Os problemas de decisão interessantes para essa teoria formam uma hierarquia de classes muito bem estruturada com problemas completos naturais:

FPTW[1 1]W[2]...W[Eu]W[Eu+1 1]...W[P]

É claro que está aberto se alguma dessas inclusões é estrita ou não. Observe que seFPT=W[1 1] then SAT has subexponential algorithm (this is non trivial). Last statement connects prameterized complexity with ETH mentioned above.

Also notice that investigating such collapses is not an empty exercise: proving that W[1]=FPT is equivalent to prove that there is a fixed parameter tractable algorithm for finding k-cliques.

MassimoLauria
fonte