Reducción de Polytime Manyone: Clique a E-TM

Requisito previo: Clique es NP
A La reducción de tiempo polinomial es un método para resolver un problema usando otro.
E-TM = {<M> : M es una TM y }
CLIQUE = {<G, k> : el grafo G tiene una camarilla con al menos k vértices}.

Nota:
dado que CLIQUE es NP => algunos NDTM _CLIQUE aceptan CLIQUE.

Reduction(<G, k>)
    construct the following machine M
    M(x):
        1. Run NDTMCLIQUE on input <G, k>.
    2. If NDTMCLIQUE accepts; M rejects x.
    3. Else; M accepts x.
    return <M>

Convertimos la instancia <G, k> CLIQUE en una TM <M> E-TM. Y <G, k> CLIQUE a una TM <M> E-TM.

Exactitud:

i. <G, k>  CLIQUE => M rejects all input x => L(M)=  => <M>  E-TM.
ii. <G, k>  CLIQUE => M accepts all input x => L(M) => <M>  E-TM.

Por lo tanto, la reducción es correcta.

Polytime:
la reducción implica describir la construcción de una nueva máquina de Turing M para la entrada <G, k>. No hacemos funcionar la máquina en la entrada. Por lo tanto, la reducción es politiempo.