NP-complétude et réductibilité

Question

Je suis assez nouveau sur ce site, je m'excuse si cette question est dans la mauvaise section. Je prends un cours d'analyse d'algorithme et je suis coincé sur un de mes problèmes de devoirs et j'apprécierais que je puisse recevoir des conseils. Le problème que je suis bloqué est de prouver que le langage vide et {0, 1} * sont les seules langues dans P qui ne sont pas complètes pour P en ce qui concerne les réductions polynomiales (problème 34.3-6 dans CLRS 3ème édition). La première partie du problème semble assez simple (prouvant les critères de langage vides). Cependant, je ne sais pas par où commencer même quand je dois prouver les critères pour {0, 1} *. Je ne cherche pas la réponse, mais j'apprécierais quelques conseils sur la façon dont je peux commencer à penser à ce problème. Merci d'avance!

Answer 1

Définition de P Exhaustivité en ce qui concerne la réduction du temps polynomiale est un problème L est P-complet si:

1. L est P
2. Il y a une réduction polynomiale de chaque problème dans P L.

pour L = {}, étant donné un problème X tel que X!= {}, vous devez trouver une réduction p telle pour chaque instance de X (laisser être x), p(x) est en L si et seulement si x est en X. Supposons qu'il existe un tel p. Cependant, depuis X != {}, il y a quelques x tels que x est dans X, et p(x) ne peut pas être dans L, puisque L est vide. Contradiction pour l'existence de tels p.

Répéter de manière similaire pour L={0,1}* avec n'importe quelle langue X != {0,1}* et x n'est pas dans X.