Pós-seleção na teoria da complexidade geométrica

Contexto: Pelo que entendi, na teoria da complexidade geométrica, a existência de obstruções serve como um certificado de prova, por assim dizer, para a inexistência de um circuito computacional eficiente para a função difícil explícita no problema de limite inferior em consideração. Agora, existem outras suposições para obstruções que devem ser curtas, fáceis de verificar e fáceis de construir.

Pergunta: Minha pergunta é: digamos que tenho um problema que suponho ser solucionável em tempo polinomial. Então, como posso mostrar que não existe obstrução para esse problema, ou seja, se não existem obstruções, o problema pode ser calculado com eficiência e é de fato no tempo polinomial.

Abordagem: Eu acho que posso estar errado nessa afirmação de que não mostrar obstruções pode ser equivalente à redução padrão de problemas de PN a outros problemas cuja complexidade ainda é desconhecida, na prova de que eles mesmos estão em PN. Então, nesse caso, pode-se, se possível, mostrar que existem obstruções quando se tenta reduzir um problema de NP ao problema considerado, dessa forma, a redução é intratável. Além disso, qual é o papel da pós-seleção nisso tudo? É possível simplesmente pós-selecionar a inexistência de obstruções? Obrigado e perdoe a falta de declarações precisas na minha abordagem e nas perguntas.

Apenas outro exemplo, considere um problema X que sabemos estar em P. Agora, digamos que não sabíamos que esse problema era solucionável em tempo polinomial, então é possível que se possa fazer a seguinte afirmação:

Como não existem obstruções no cálculo de X , podemos dizer que está na classe P

A partir daí, o problema é a fácil descoberta (computacionalmente) dessas obstruções, se houver uma, mostraria que X não está no tempo polinomial. No entanto, seguindo o caminho inverso, ou seja, descobrir que não existem obstruções é uma tarefa difícil.

Depende do que você quer dizer com "não existe obstrução". Se você quer dizer "obstrução" no sentido geral de algum tipo de certificado de prova de que o problema não está em , não tenho idéia de como responder à sua pergunta, porque a noção de "obstrução" ainda é vaga. Se você quer dizer "obstrução" especificamente no sentido teórico da representação de Mulmuley-Sohoni, então aqui está a resposta:$P$

Para os fins desta resposta, podemos particionar o programa Mulmuley-Sohoni GCT em duas etapas:

1. Associe-se às variedades algébricas e (ou suas classes de complexidade favoritas) e forma que se e somente se for uma proteção de .$perm$$det$$V_{perm}$$V_{det}$$V_{perm} \subseteq V_{det}$$perm$$p$$det$

2. Encontre obstruções teóricas da representação para mostrar que, de fato, .$V_{perm} \not\subseteq V_{det}$

Observe que a implicação em (2) segue apenas uma direção (a existência de obstrução não implica a inclusão de variedades); portanto, é possível que não seja uma projeção de e ainda não exista obstruções teóricas da representação. Portanto, neste caso, apenas provar que não existem obstruções não é suficiente para mostrar que é fácil. Por outro lado, em (1) a inclusão de variedades algébricas é necessária e suficiente para a inclusão de classes de complexidade.$perm$$p$$det$$perm$

[No curso acima, muitos detalhes foram omitidos - a dependência do tamanho da entrada, como falar sobre a classe de complexidade vez de , o fato de que a inclusão de variedades é equivalente a ser aproximada pelas projeções de , ... Mas a essência ainda está certa.]$P$$det$$perm$$p$$det$

Também gosto de pensar assim e conjectura . É mencionado lá ou ali (estou tendo dificuldade em encontrar páginas sobre essa conjectura, pois só posso me referir a ela com símbolos matemáticos que o Google não gosta).$P=NP\cap co-NP$

Um problema está no NP quando você pode fornecer um certificado para uma resposta "Verdadeira" (exemplo: um ciclo hamiltoniano para o problema TSP ou uma atribuição válida para o problema SAT). É no co-NP quando você pode dar um certificado para uma resposta "Falsa" (exemplo: uma "prova" de que a fórmula SAT não é satisfatória, um corte incorreto em um gráfico que impede a existência de um ciclo hamiltoniano etc.) ..)

Na verdade, essas podem ser as "obstruções" que você também pode se referir. E essa conjectura é sobre dizer: um problema que está em NP é polinomial quando eu sei quais são as obstruções.

Agora, as "obstruções" podem assumir muitas formas diferentes. Para o problema de correspondência (que é polinomial), pode ser uma partição do gráfico (consulte a caracterização de Tutte pelos gráficos que admitem uma correspondência perfeita ) ou pode ser o certificado fornecido pelo Lemma de Farkas para programação linear (e problemas gráficos que podem ser reduzidos para ele). Na verdade, pode ser um grande número de coisas, e por isso geralmente "uso" essa conjectura em uma direção: quando não encontro obstruções, não deduzo que meu problema seja NP-Hard. Algumas obstruções são realmente difíceis de encontrar ... Mas quando tenho um algoritmo polinomial complicado para um problema, às vezes estou convencido de que "deve haver um conjunto compreensível de obstruções, o que seria mais fácil de entender que o algoritmo complicado".

Bem ... Meus dois centavos :-)

Nathann