O APX está contido no NP?

15

Diz-se que um problema P está no APX se existir alguma constante c> 0, de modo que exista um algoritmo de aproximação em tempo polinomial para P com fator de aproximação 1 + c.

O APX contém PTAS (visto simplesmente escolhendo qualquer constante c> 0) e P.

O APX está no NP? Em particular, a existência de um algoritmo de aproximação em tempo polinomial para algum fator de aproximação implica que o problema está em NP?

cc.complexity-theory complexity-classes apx Andrew W.
fonte
Penso que "o que se sabe sobre a classe X em relação a todas as outras classes Y" é muito vago como questão, a menos que sejam fornecidos mais detalhes sobre os tipos de relacionamentos buscados.
András Salamon
Quero dizer relacionamentos como 'contém', 'está contido em', 'não contém'.
Andrew W.
Depois de algum pensamento, eu reduzi a questão baixo para a relação específica que estou mais interessado.
Andrew W.
11
O que exatamente significa perguntar se o APX está contido no NP? O APX consiste em problemas aproximados de "otimização de NP", enquanto o NP consiste em problemas de decisão. Além disso, por definição, a versão de decisão de um problema de otimização do NP está no NP. Talvez você tenha algo em mente?
Joshua Grochow
Você está certo, Joshua. Ian respondeu à pergunta que eu deveria ter feito.
Andrew W.

Respostas:

20

O APX é definido como um subconjunto do NPO; portanto, se um problema de otimização estiver no APX, o problema de decisão correspondente estará no NP.

No entanto, se o que você está perguntando é se um problema arbitrário deve estar no NP (ou NPO) se houver uma aproximação de tempo poli (O) 1, a resposta é não. Não conheço nenhum problema natural que sirva de contra-exemplo, mas é possível definir um problema de maximização artificial em que o objetivo é a soma de dois termos, um termo amplo que é facilmente otimizado em P e um termo muito menor isso adiciona uma pequena quantia se parte da solução codifica uma resposta para algum problema difícil (fora do NP). Então, você pode encontrar, por exemplo, uma aproximação de 2 no tempo poli, concentrando-se no termo fácil, mas encontrar uma solução ideal exigiria a solução do difícil problema.

Ian
fonte
2
Aceitei sua resposta porque ela abordava tanto a pergunta que eu fiz ('O APX está contido no NP?') Quanto a pergunta que eu deveria ter perguntado ('Um poli-tempo O (1) implica aproximadamente uma solução exata no NP?').
Andrew W.
11
Uma ampla classe de problemas que não estão contidos no NPO e no NP, mas possuem aproximação de fator constante é a classe de problemas on-line (a questão sobre qual classe de complexidade contém problemas on-line é aqui: cstheory.stackexchange.com/questions/1664/… ) .
Oleksandr Bondarenko