Per quali valori di A e B è il problema gap-VC [A, B] NP-hard?

Question

Per quali valori $ A, B $ è il problema $ \ {mathsf gap \ mathord-VC} \ mathord- [A, B] $ NP-hard? VC è la vertice problema della copertura . Mi sono dato tre opzioni: $ B = \ frac {3} {4}, A = \ frac {1} {2} $ o $ B = \ frac {3} {4}, A = \ frac {1} { 4} $ o nessuno.

vorrei rivedere quello che penso che ho bisogno di fare, io non sono sicuro che il mio modo di pensare di esso è corretto. Questo è quello che penso: ho bisogno di decidere se NP-hard, sul ravvicinamento del VC a $ \ frac {1} {2} $, vale a dire, posso costruire una macchina NP Turing che sarebbe tornato Sì se e solo se per un dato grafico, si può garantire che esso ha meno di $ \ frac {1} {4} V $ vertici che coprono l'intero grafico? Forse anche per $ \ frac {1} {2} V $ vertici?

_{Questa è una domanda da un medio termine passato che sto risolvendo ora per prepararmi per il mio medio termine in un corso "Computational Complexity Theory".}

Answer 1

copertura Vertex ha un facile $ 2 $ -approximation, così gap-VC - [$ 1 / 4,3 / 4 $] è facile. Il miglior risultato di durezza incondizionato è di Dinur e Safra, che dà $ 1,3606 $ durezza. Dal momento che $ (3/4) / (1/2) = 1,5> 1,3606 $, il loro metodo sicuramente non implica gap-VC - [$ 1 / 2,3 / 4 $] - durezza. Supponendo che l'Unique Games congettura, la durezza della copertura dei vertici è $ 2- \ epsilon $, ma questo non implica necessariamente che gap-VC - [$ 1 / 2,3 / 4 $] è difficile - che ci si deve guardare la prova per determinare questo.

In sintesi, non ho idea di quale sia la risposta corretta è, e non sono sicuro che chiunque altro sa che risposta è corretta (incondizionatamente).