But de randomisation / derandomisation dans l'algorithme randomisé de base pour Max Sat

Question

dans les sections 5.1 de La conception des algorithmes d'approximation par Williamson et Shmoys, ils décrivent un Algorithme randomisé de base pour Max Sat et comment le dériver. L'algorithme est juste d'attribuer chaque variable 1 (vraie) avec probabilité 1/2 et 0 (false) avec probabilité 1/2. En d'autres termes, échantillon uniformément au hasard de l'espace de toutes les solutions. Ils montrent qu'il s'agit d'une approximation de 1/2.

Puis dans la section 5.2, ils décrivent comment le dérommuer en utilisant la méthode des attentes conditionnelles. (Je ne vais pas décrire le processus ici car il n'est pas très complexe et largement connu que je suppose.)

ma question est, pourquoi la dérangeez-vous de cette façon? Ou même, pourquoi prendre la peine de faire l'algorithme au hasard dans la première place?

Il me semble qu'un algorithme tout aussi bon serait la doublure qui définit de manière déterministe toutes les variables à 1. Compte tenu de l'instance Max Sat en entrée, il me semble que vous vous attendriez également à ce que cela (c'est-à-dire " l'attente qu'il serait ") satisfaire la moitié des clauses. Pour moi, l'analyse de l'algorithme aléatoire semble vraiment dire que toute hypothèse est "bonne". (Plutôt que de montrer que notre algorithme aléatoire est intrinsèquement bon.) Alors pourquoi traverser le processus de randomisation et de derandomisation en premier lieu?

Merci d'avance!

Answer 1

La différence est que l'algorithme randomisé garantit une approximation attendue 1/2 - sur toute entrée . En revanche, il est facile pour un adversaire de construire une entrée (c'est-à-dire une instance de max-sam) pour laquelle la déterministe "Définir toutes les variables à un vrai" algorithme stitisife zéro clauses.

N'oubliez pas que l'espace d'échantillonnage d'un algorithme randomisé est sur un ensemble de bits aléatoires auxiliaires. Il n'y a pas de distribution de probabilité supposée sur les entrées . L'objectif typique de la conception d'algorithmes randomisés est que chaque entrée soit manipulée bien dans l'attente. (Analyse du comportement d'algorithme sur une distribution d'entrée supposée s'appelle analyse moyenne de cas à la place.)

Quels sont les bits aléatoires auxiliaires?

Supposons que nous ayons une machine de turing randomisée $ m_1 $ qui fonctionne sur des instances de longueur $ n $ pour plus de $ T (n) $ temps, au cours de laquelle il ne fait plus que $ r (n) \ le T (n) $ décisions aléatoires. Nous pouvons transformer cette machine en une machine Turn Turing $ M_2 $ qui comporte deux bandes d'entrée: la bande habituelle contenant la chaîne d'entrée $ x $ de longueur $ n $ et une bande contenant une chaîne $ R $ de longueur $ r (n) $ . La chaîne $ r $ est notre chaîne de bits aléatoires auxiliaires ; Il détermine les décisions "aléatoires" que la machine Turing est à faire. Lorsque nous disons que la machine Turning Turing exécute $ m_1 (x) $ accepte avec probabilité $ p $ , Cela équivaut à dire que l'ensemble $$ a (x)=gaucher \ {r \ | \ r \ in \ {0, 1 \} ^ {r (| x |)}, m_2 (x, r ) \ texte {accepte} \ right \} $$ de $ R $ cordes qui font $ m_2 (x, r) $ accepte constitue une fraction $ p= | A (x) | / 2 ^ {| x |} $ de l'ensemble de tous $ r $ cordes.

Vous pourriez reconnaître ce qui se passe ici si vous avez vu la construction analogue pour des machines à troubles non déterministes. Nous pouvons penser à une machine NP comme une machine non déterministe qui se branche de nombreuses copies de manière exponentielle. Mais nous pouvons également y penser comme une machine déterministe vérificatif qui nécessite à la fois une chaîne d'entrée et une "épreuve", avec les critères d'acceptation qu'une chaîne d'entrée est dans la langue si tout La chaîne de preuve fait accepter la machine.

Il est souvent plus facile de penser à ce concept de Verificateur déterministe et que le sous-ensemble de chaînes de preuve rend la machine accepter sur une entrée donnée, plutôt que de penser à des idées très abstraites comme des machines de ramification exponentielle et des mondes possibles. . Et il est plus facile de définir des cours de complexité tels que CO-NP, PP, BPP, PP, etc., qui sont essentiellement «NP ayant une règle d'acceptation différente». Par exemple:

• np est l'ensemble de langues $ l $ pour laquelle il existe une machine de vérificateur de temps polynomial $ m_2 $ < / span> tel que $ x \ in l $ si et seulement s'il existe un $ r $ string telle que $ m_2 (x, r) $ accepte (où la longueur de la $ r $ string est délimité par un polynôme $ r (| x |) $ ).
• BPP est l'ensemble des langues $ l $ pour lequel il existe une machine de vérificateur de temps polynomial $ m_2 (x , r) $ tel que $ x \ in l $ implique que $ m_2 (x, r) $ accepte d'au moins ⅔ de $ R $ cordes et $ x \ notin l $ implique que $ m_2 (x, r) $ accepte au plus ⅓ de $ r $ cordes (où le Longueur de la $ R $ Strings est délimitée par un polynôme $ r (| x |) $ ).

Remarque: il n'a pas d'importance, si nous avons besoin de la $ R $ Strings pour avoir de la longueur exactement $ r (n) $ ou au plus $ r (n) $ , puisque, car permettant à des cordes plus courtes que augmente le nombre de cordes possibles par un facteur constant.