Revisão da minha prova de que a Co-NP != P

Question

Este é o hobby de trabalho, não é o meu trabalho. Eu escrevi esse trecho para compartilhar algumas idéias sobre a Co-NP.

A ideia é escolher uma categoria de problema em Co-NP, onde a resposta correta é difícil verificar por causa da complexidade do circuito, a expressamos como é de 1 em k SAT fórmula, e mostram, também existe um curto certificado, cujo comprimento em bits é exatamente o dobro do número de cláusulas.Ele pode ser verdadeira ou falsa, de que todos os Co-NP problemas têm um período tão curto de certificado desta forma (Co-NP ?= NP), mas eu mostram que, independentemente do que, a curto certificado para este problema pode ser feita arbitrariamente difícil de encontrar, porque de intercalados relação com a NP.Basicamente, eu quero destacar uma determinada dependência circular entre os oráculos de NP e Co-NP.O argumento para se bater contra a Co-NP = P é que não TM pode esperar para atacar o problema de pesquisa para o curto certificado em subexponential tempo, porque a maneira como eu definir o problema torna conter uma quantidade arbitrária de "real aleatório".Basicamente, é uma receita específica para criar um "monstro" Co-NP problema a partir de um simples certificado.

Agora eu tenho muitas perguntas para qualquer pessoa com um treinamento mais formal do que a mim:

• Tem essa categoria de problema foi expresso com um nome diferente?
• Trata-se de um óbvio ponto morto ou inexploradas?
• Como posso expressar as mesmas idéias, mas mais formalmente contra TM capacidades?

Answer 1

WTLU está em P.

algoritmo:

• Faça o monótono de 1-in-K SAT adicionando uma cláusula para cada par de literais (x + ~ x)= 1 e substituindo ~ x por uma nova variável.
• Escolha um grande prime P, pelo menos maior que o número de cláusulas.
• Gire a fórmula 1-in-k em um sistema de equações lineares Modulo P.Cada cláusula original no formulário (x, y, z ...)= 1 se torna uma equação (x, y, z ...)= 1 mod p.
• Realize a eliminação gaussiana.
• Se a fórmula foi uma instância WTLU, então uma contradição é encontrada antes que o formulário Echelon de linha seja atingido, na forma de uma equação contraditória 0= k mod p (com k!= 0).

por que funciona:

Se houver dois conjuntos de cláusulas que cobrem o mesmo conjunto de literais, tal que (C1 + C2 + C3 ...)= X e (C1 '+ C2' + C3 '...)= Y e X!= Y, então é também o caso Modulo P.Assim, o sistema de equações Modulo P não é satisfatório também.

Answer 2

Aqui está um contra-argumento.Uma prova similar estrutura, poderia ser facilmente usado para provar que XOR-SAT é difícil.

1. Tomar um unsatisfiable XOR-SÁB fórmula com um grande espaço.Você não pode resolvê-lo com uma resolução-como algoritmo.

2. Agora existe um curto unsatisfiability certificado, porque XOR-SAT é em P.

3. Se você não sabe sobre a eliminação, em seguida, combinar aleatório cláusulas juntos até duas cláusulas tenham as mesmas variáveis, uma linha é igual a zero e a outra linha é igual a um.Forro até é um caso particular da adição onde as cláusulas não literais em comum.

4. Adicionar aleatório cláusulas e variáveis para o XOR-SÁB fórmula para torná-lo mais difícil aleatoriamente para fazer as coisas.

Mas, na realidade, você pode fazer a Eliminação Gaussian em um polinˆ omio quantidade de tempo e de espaço até duas linhas cancelar o outro para produzir a 0=1.

Para expandir o seu argumento e torná-lo interessante, você precisaria, no mínimo, mostrar que existe uma diferença fundamental com XOR-SÁB, para começar, que não há um processo semelhante para a eliminação de onde você pode tirar as variáveis uma a uma durante o processo de isolar o 2 conflituosa conjuntos de cláusulas ignorando a informação extra.