Dureza de aproximação assumindo NP! = CoNP

Duas das suposições comuns para provar resultados de dureza de aproximação são e Unique Games Conjecture. Existe alguma dureza de resultados de aproximação assumindo ? Estou procurando o problema modo que "é difícil aproximar um fator menos que ".$P \neq NP$$NP \neq coNP$$A$$A$$\alpha$$NP = coNP$

Sabe-se que "mostrar dureza NP do fator para o menor problema vetorial implicaria ". Observe que este é o "oposto" do que estou procurando.$n$$NP = coNP$

Esclarecimento: É possível que e ainda a questão P vs NP esteja aberta. Estou procurando resultados de dureza de aproximação que se tornarão falsos se mas não for afetado (isto é, ainda permanece como uma conjectura) por .$NP=coNP$$NP=coNP$$P \neq NP$

Aqui está uma observação direta. Se você assumir , é bem fácil perceber que existem problemas de otimização de N P que nem sequer têm bons algoritmos de aproximação não determinísticos , em algum sentido.$NP \neq coNP$$NP$

Por exemplo, o teorema do PCP diz que você pode traduzir SAT no problema de distinguir se das cláusulas são satisfeitas e todas as cláusulas são satisfeitas, para alguns ε > 0 . Suponha que exista um algoritmo não determinístico que possa distinguir entre esses dois casos, no sentido de que o algoritmo não determinístico pode relatar em cada caminho de computação "todos satisfeitos" ou "no máximo 1 - ε ", e diz "no máximo 1 - ε" "em algum caminho, se no máximo 1 - $1-\varepsilon$$\varepsilon > 0$$1-\varepsilon$$1-\varepsilon$$1-\varepsilon$pode ser satisfeito, caso contrário, diz "todos satisfeitos" em todos os caminhos de computação se todas as equações puderem ser satisfeitas. Isto é suficiente para decidir sab em , de modo N P = C O N P . Parece claro que a existência de um tal algoritmo não-determinístico não tem nenhuma influência sobre se P = N P .$coNP$$NP=coNP$$P = NP$

É bastante plausível que existe um cenário mais "natural": um problema de otimização que é difícil aproximar em determinístico de tempo polinomial sob , mas não conhecido por ser duro sob P ≠ N P . (Provavelmente, é isso que você realmente deseja perguntar.) Muitos resultados de dureza de aproximação são comprovados primeiro sob uma premissa mais forte (por exemplo, N P não em tempo subexponencial ou N P não em B P P ). Em alguns casos, melhorias posteriores enfraquecem a suposição necessária, às vezes até P ≠ $NP \neq coNP$$P \neq NP$$NP$$NP$$BPP$ . Portanto, há esperança de que haja uma resposta um pouco mais satisfatória do que esta. É difícil imaginar como poderia haver um problema quenão podeser provado difícil aproximado em polytime determinista sob P ≠ N P , maspodeser provado duro sob N P ≠ c o N P . Isso significaria que N P ≠ c o N P nos diz algo sobre cálculos determinísticos que P ≠ N P ainda não diz; intuitivamente, isso é difícil de entender.$P \neq NP$$P \neq NP$$NP \neq coNP$$NP \neq coNP$$P \neq NP$

Disclaimer: esta não é uma resposta direta.

Na verdade, existem muito mais condições de dureza além de P! = NP e UGC. David Johnson escreveu uma bela coluna para as Transações sobre algoritmos em 2006, precisamente sobre esta questão. Ele lista as inúmeras suposições diferentes usadas para mostrar dureza e como elas se relacionam.

Infelizmente, essas são todas NP versus classes determinísticas (com exceção de NP e co-AM). NP vs co-NP não é totalmente coberto.

é uma hipótese mais forte que P ≠ N P desde N P ≠ C O N P implica P ≠ N P . Portanto, qualquer resultado de dureza de aproximação assumindo P ≠ N P também se seguiria dasuposição N P ≠ c o N $NP \ne coNP$$P \ne NP$$NP\ne coNP$$P\ne NP$$P\ne NP$$NP\ne coNP$

Esta não é uma resposta direta

O problema de escolha de k é $\prod_2^P$-completo. Sob a suposição de que $NP \ne coNP$, k-Choosability é estritamente mais difícil que k-Coloring em gráficos gerais. Portanto, aproximar o número cromático da lista é estritamente mais difícil que o número cromático. Sabe-se que a coloração k é trivial para gráficos bipartidos. Entretanto, determinar o número cromático da lista de gráficos bipartidos é$NP$-Difícil. (mesmo a 3-Chooseability é$\prod_2^P$-completo)

Noga Alon, Corantes restritos de gráficos