Problemas no NC desconhecidos por NC2

14

Existem problemas interessantes em mas não em N C 2 ? No artigo 'A Taxonomy of Problems With Fast Parallel Algorithms', Cook menciona que MIS era conhecido por estar apenas em N C 5, mas isso foi reduzido a N C 2 . Eu estou querendo saber se existem outros problemas com algoritmos paralelos de profundidade de polilog onde parecemos estar presos em melhorar a profundidade.NCNC2NC5NC2

Para diminuir ainda mais, existem problemas em que não se sabe estar em A C 1 ou D E T ?NC2AC1DET

xal
fonte
1
Veja esta pergunta e a resposta de Josh.
Kaveh 21/07
Perdi completamente isso Kaveh --- obrigado! O último parágrafo da resposta em e o colapso hierarquia correspondente dá intuição útil para o estado de N C . NL=coNLNC
XAL
Na verdade, eu estava apenas pensando sobre sua pergunta final; Eu acho que valeria a pena postar como uma pergunta separada (já que é tecnicamente uma questão diferente e independente da pergunta em seu título). xal, estaria aberta para enviar mensagens a causa de problemas em não conhecido por ser em ( A C 1D E T ) como uma questão separada? E @Kaveh, o que você acha de fazer isso do ponto de vista processual? NC2(AC1DET)
Joshua Grochow
@ Josh, não vejo nenhum problema em fazê-lo. Pedimos aos autores que dividissem as perguntas em postagens separadas antes.
Kaveh
1
Obrigado por perguntar a Josh, eu divido a pergunta aqui: cstheory.stackexchange.com/q/39831/40340
xal

Respostas:

13

Aviso Legal: eu não sou especialista em algoritmos paralelos rápidos, portanto, a probabilidade de que eu tenha perdido resultados mais recentes que colocam os problemas mencionados em níveis mais baixos da hierarquia NC não é desprezível. Se você observar que é esse o caso, informe-me e atualizarei minha resposta.

  • O relatório Algoritmos Paralelos para Pesquisa em Profundidade Primeiro discute algoritmos paralelos conhecidos para DFS em vários tipos de gráficos. A lista fornecida nas páginas 9-10 indica vários algoritmos em NCNC2 , como DFS para gráficos não direcionados planares ou em RNCRNC2 , como DFS para gráficos não direcionados gerais.

  • Com uma pesquisa rápida, não foi possível encontrar artigos aprimorando os algoritmos paralelos para interpolação polinomial esparsa multivariada em campos finitos deste artigo , que está emNC3 . No entanto, vários documentos que poderiam ter sido relevantes estavam por trás de um paywall.

  • A computação de todas as cliques máximas em um gráfico está em NCNC2 quando o número demáximos é polinomialmente limitado, de acordo comeste artigo.

  • O problema do caminho máximo parece estar emNC5 para gráficos gerais (não direcionados), não encontrei algoritmos paralelos mais rápidos sem restrições no gráfico subjacente.

Outros candidatos em potencial podem incluir algoritmos para encontrar combinações perfeitas em tipos específicos de gráficos ou algoritmos para encontrar uma cobertura máxima de árvore em gráficos arbitrários (por exemplo, este artigo menciona algoritmos polytime aleatórios em tempo paralelo O(log6n) ). Este artigo também menciona a solução de classes de problemas de CSPs que surgem no aplicativo de visão computacional, em tempo paralelo O(log3n) .

Geoffroy Couteau
fonte
1
Interessante! Você sabe se algum deles está completo (ou conjecturado como completo) para esses níveis mais altos da hierarquia NC? Seria bom ter exemplos naturais à mão.
Joshua Grochow 18/09/19
Infelizmente, eu não tenho idéia disso, os trabalhos que listei acima não mencionam nada do tipo (tanto quanto posso ver). Tudo isso está muito longe da minha área de especialização; Eu apenas fiz uma pesquisa bibliográfica para responder à pergunta da OP, pois achei muito interessante, mas meu conhecimento limitado não me dá nenhuma intuição clara sobre a dureza desses problemas.
Geoffroy Couteau