Metodi per dimostrare il limite superiore su algoritmi di approvvigionamento A? [Chiuso

Question

Ho a che fare con alcuni semplici algoritmi randomizzati e online, entrambi tipi producono un limite inferiore/superiore sulla qualità dell'istanza di output.

Ad esempio, esiste un semplice algoritmo randomizzato per il Max-e3sat Problema, dove ci sono clausole $ m $ ciascuna composta da tre distinte 3 variabili in $ {x_1, ..., x_n } $.

C'è un teorema che se esiste un algoritmo che è $ ( frac {7} {8} + epsilon) $-approssimazione, allora $ p = np $.

Quale metodo può e dovrei usare per dimostrare tali teoremi? Potresti fornire un esempio?

Più sopra, per quanto riguarda il Max-e3sat Problema, quale metodo può e dovrei usare per dimostrare tale affermazione:

Per qualsiasi caso di Max-e3sat L'ottimale è almeno $ frac {7m} {8} $? Non sto cercando la prova di questa affermazione, solo il metodo per dimostrarlo.

Molte grazie