Polytime Manyone reduction: Clique to E-TM
Note –
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>
Correctness:
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.
Polytime –
Contact Us