Deixe ser o idioma de todos os 2 -cnf fórmulas φ , de tal modo que, pelo menos, ( 1dascláusulasdeφpodem ser satisfeitas.
Preciso para demonstrar que existe r L ε é N P -Hard para qualquer ε < ε ' .
Sabemos que o pode ser aproximado a 55 das cláusulas de umaredução deMax3Sat. Como devo resolver este?
Em seu famoso artigo, Hastad mostra que é NP-difíceis de MAX2SAT aproximado melhor do que . Isso provavelmente significa que é é NP-difícil distinguir ocorrências que são ≤ α satisfatível e exemplos que são ≥ ( 22 de / 21 de ) α satisfatível, para alguns α ≥ 1 / 2 . Agora imagine acolchoar uma instância para que se torne um p -fraction de uma nova instância, o resto do que é exatamente 1 / 2 -satisfiable (dizem que consiste em grupos de cláusulas de forma a ∧ ¬ ) Os números agora tornar-se 1 / 2 + p ( α - 1 / 2 ) e 1 / 2 + p ( ( 22 de / 21 de ) α - 1 / 2 ) . Este último número pode ser feita como perto de 1 / 2 como nós queremos.
Se você sabe que ε é um número racional, não precisa de uma inadequação para Max-2-SAT para provar sua afirmação. Uma prova típica da dureza NP do Max-2-SAT (por exemplo, a do livro Complexidade computacional de Papadimitriou) na verdade prova a completude NP de L 1/5 . Para provar que o NP-dureza de L ε para positivo racional números ε <1/5, podemos reduzir G 1/5 a G ε como se segue: uma dada fórmula 2CNF φ (um exemplo para G 1/5 ), deixá- m ser o número de cláusulas nele. Vamos r es sejam inteiros positivos, de modo que (1 / 5− ε ) mr = 2 ε s seja válido. Em seguida, construa uma fórmula 2CNF (uma instância para L ε ) repetindo φ por r vezes e adicionando s pares de cláusulas contraditórias. Um cálculo simples mostra que essa é realmente uma redução de L 1/5 para L ε .
Essa redução claramente funciona apenas se ε for racional, porque de outra forma r e s não podem ser tomados como números inteiros. O caso geral em que ε não é necessariamente racional parece exigir inadequação, como Yuval Filmus escreveu em sua resposta.
fonte