Les types de réductions et définitions associées de dureté

Question

Soit A à B réductible, à savoir $ A \ leq B $. Par conséquent, la machine de Turing accepter $ A $ a accès à un oracle pour $ B $. Laissez la machine de Turing accepte $ A $ soit $ M_ {A} $ et l'oracle pour $ B $ soit O_ $ {B} $. Les types de réductions:

• Réduction Turing:. $ M_ {A} $ peut faire plusieurs requêtes à O_ $ {B} $

• Réduction Karp: Aussi appelé "réduction de Turing polynomiale": L'entrée à $ O_ {B} $ doit être construit en polynomial. De plus, le nombre de requêtes à $ O_ {B} $ doit être délimitée par un polynôme. Dans ce cas:. $ P ^ {A} = P ^ {B} $

• De nombreux-une réduction Turing: $ M_ {A} $ peut faire une seule requête à $ O_ {B} $, au cours de sa dernière étape. D'où la réponse oracle ne peut pas être modifié. Cependant, le temps nécessaire pour construire l'entrée à $ O_ {B} $ n'a pas besoin d'être limitée par un polynôme. De manière équivalente: ($ \ leq_ {m} $ indiquant la réduction many-one)

    

  $ A \ leq_ {m} B $ si $ \ existe $ une fonction calculable $ f: \ Sigma ^ {\ ast} \ to \ Sigma ^ {\ ast} $ tel que $ f (x) \ in B \ ssi x \ in A $.

• Réduction de cuisson: Aussi appelé « temps polynomial beaucoup-on réduction »: Un grand nombre-une réduction où le temps nécessaire pour construire une entrée à $ O_ {B} $ doit être délimitée par un polynôme. De manière équivalente: ($ \ leq ^ {p} _ {m} $ indiquant many-une réduction)

    

  $ A \ leq ^ p_ {m} B $ si $ \ existe $ poly-temps fonction calculable $ f: \ Sigma ^ {\ ast} \ à \ Sigma ^ {\ ast } $ tel que $ f (x) \ in B \ ssi x \ in A $.

• Réduction parcimonieux: Aussi appelé "one-one réduction du temps polynomiale": Une réduction de Cook où chaque instance de $ A $ mis en correspondance avec une instance unique de $ B $. De manière équivalente: ($ \ leq ^ {p} _ {1} $ indiquant la réduction parcimonieuse)

    

  $ A \ leq ^ p_ {1} B $ si $ \ existe $ poly-temps calculable bijection $ f: \ Sigma ^ {\ ast} \ à \ Sigma ^ {\ ast } $ tel que $ f (x) \ in B \ ssi x \ in A $.

  Ces réductions préserver le nombre de solutions. Par conséquent $ \ # M_ {A} = \ #O_ {B} $.

On peut définir plusieurs types de réductions par limitant le nombre de requêtes d'oracle, mais en laissant les sortir, quelqu'un pourrait bien vouloir me dire si je l'ai obtenu la nomenclature pour les différents types de réductions utilisées, correctement. Sont des problèmes NP-complets définis par rapport réduction Faire cuire ou à la réduction parcimonieuse? Quelqu'un peut-il bien vouloir donner un exemple d'un problème qui est NP-complet sous Cook et non en réduction parcimonieuse.

Si je ne me trompe pas, la classe #-P complète est définie par rapport à des réductions Karp.

Answer 1

Votre définition de réductions parcimonieuses est incorrecte. Vous confondez avec un temps un polynôme réduction qui est un cas particulier de réductions Karp. Ils ne conservent pas le nombre de « solutions ». S'il vous plaît voir cette réponse pour plus sur des réductions en tenant compte du nombre de certificats.

Le reste semble bon, mais il est généralement préférable de les voir dans un tableau à deux dimensions:

• la complexité de la réduction. Calculable, polynomiale, espace logarithmique, etc
• type d'accès: Turing, beaucoup-un, un-un, etc.

  

Les problèmes sont-NP-complets définis par rapport réduction Faire cuire ou à la réduction parcimonieuse?

$ \ mathsf {NP} $ dureté et l'exhaustivité sont définies w.r.t. réductions Karp (polynomial beaucoup un), cuisinez pas, ni les réductions parcimonieuses.

  

Quelqu'un peut-il bien vouloir donner un exemple d'un problème qui est NP-complet sous Cook et non en réduction parcimonieuse.

Prenez le complément de SAT, il est complet pour $ \ mathsf {NP} $ dans le cadre des réductions Cook, on ne croit pas être complet pour $ \ mathsf {NP} $ dans le cadre des réductions Karp. réductions Karp comprennent un-un polynomial réductions.

  

la classe #-P complète est définie par rapport à des réductions Karp

Notez que $ \ mathsf {\ # P} $ n'est pas classe problèmes de décisions, il est une classe de problèmes de calcul de la fonction. Sa dureté et l'exhaustivité sont généralement définis w.r.t. réductions Cook (polynomial). Turing Voir par exemple Arora et Barak, à la page 346.

Answer 2

La définition de la réduction Karp est incorrecte. Une réduction Karp est une réduction de Turing polynomial dans lequel l'oracle $ O_B $ est appelée exactement une fois, au cours de la dernière étape des réductions.