Une réduction polynomiale de tout problème NP-complet au PCP borné

Partout, les manuels supposent que le problème de la correspondance de poste borné est NP-complet (pas plus de $N$ index autorisés avec répétitions). Cependant, nulle part on ne montre une réduction du temps polynomiale simple (comme dans quelque chose qu'un étudiant peut comprendre) d'un autre problème NP-complet.

Cependant, chaque réduction à laquelle je peux penser est exponentielle (par $N$ ou par la taille de la série) dans l'exécution. Peut-être peut-on montrer qu'il est réductible à SAT?

Comme c'est souvent le cas avec les réductions de NP, il est logique de rechercher des problèmes similaires . En particulier, il est difficile de coder des conditions globales telles que "ont vu des nœuds" dans PCP (avec de nombreuses tuiles polynomiales) ce qui contre-indique les problèmes de graphe, les problèmes d'emballage nous obligeraient à coder des nombres unaires dans PCP (créant une instance exponentiellement grande), et bientôt. Par conséquent, un problème de chaîne avec uniquement des restrictions locales peut fonctionner de manière optimale.

Considérez la version de décision du problème de superséquence le plus court :

Étant donné deux chaînes $a,b \in \Sigma^+$ avec $|a|=n$ et $|b|=m$ et , décidez s'il y a une chaîne avec tel que et sont des sous-séquences de . c ∈ Σ + | c | ≤ k a b $k \in \mathbb{N}$$c \in \Sigma^+$$|c| \leq k$$a$$b$$c$

L'idée est de laisser PCP construire des superséquences de et de gauche à droite, encodant dans les chevauchements des tuiles à quelle position nous sommes respectivement en et . Il utilisera une tuile par symbole en , donc correspond à la limite du BPCP: si nous pouvons résoudre ce PCP avec tuiles, vous pouvez lire la super-séquence commune de longueur égale, et vice versa.b a b c k ≤ $a$$b$$a$$b$$c$$k$$\leq k$

La construction des carreaux est un peu fastidieuse, mais assez claire. Notez que nous ne créerons pas de tuiles qui ne transmettent pas ou ; celles-ci ne peuvent jamais faire partie d'une super-séquence commune la plus courte, elles sont donc superflues. Ils peuvent facilement être ajoutés sans casser les propriétés de la réduction.$a$$b$

Les nombres dans les chevauchements sont codés en binaire, mais en utilisant des symboles en dehors de et en les remplissant à une longueur commune . Ainsi, nous nous assurons que les tuiles sont utilisées comme le suggèrent les graphiques (tetris), c'est-à-dire que les caractères et les chevauchements d'indexation ne se mélangent pas (PCP n'empêche pas cela en soi). Nous avons besoin:$\Sigma$$\log \max(m,n)$

• Tuiles de départ: peut commencer par , ou les deux s'ils sont égaux.a 1 b $c$$a_1$$b_1$
• Tuiles intermédiaires: peut passer au symbole suivant en , en ou les deux s'ils sont égaux.a $c$$a$$b$
• Tuiles terminales: se termine par le dernier symbole de (si le dernier de a déjà été vu), similaire à , ou par le dernier symbole des deux.a b $c$$a$$b$$b$

Ce sont les schémas de tuiles. Notez que les tuiles intermédiaires doivent être instanciées pour toutes les paires . Comme mentionné ci-dessus, créez les tuiles sans uniquement si les caractères respectifs dans et correspondent.∗ a $(i,j) \in [n]\times [m]$$*$$a$$b$

^{[ source ]}

Les sont symboliques pour "ne se soucient pas"; dans les tuiles réelles, l'autre symbole devra y être copié. Notez que le nombre de tuiles est en et chaque tuile a une longueur , donc l'instance BPCP construite (sur l'alphabet plus les symboles de séparation) a une taille polynomiale. De plus, la construction de chaque tuile est clairement possible en temps polynomial. Par conséquent, la réduction proposée est en effet une transformation polynomiale valide qui réduit le problème de superséquence commune NP-complet le plus court au BPCP.Θ ( m n ) 4 log max ( m , n ) + 1 Σ ∪ { 0 , 1 $*$$\Theta(mn)$$4\log \max(m,n) + 1$$\Sigma \cup \{0,1\}$

Je pense que vous pouvez prouver que le BPCP est NP-complet en utilisant une réduction similaire à celle utilisée pour prouver son indécidabilité. Nous prouverons directement que BPCP est NP-complet en montrant comment réduire tout problème en NP en temps polynomial.

La réduction standard utilisée pour prouver que le PCP est indécidable ( esquissée ici ) fonctionne en construisant une série de tuiles de sorte qu'il existe une solution PCP ssi il y a un calcul acceptant d'un TM donné sur une chaîne . Le nombre de tuiles créées dans cette réduction est polynomialement important - en particulier, le nombre de dominos construits est fonction de la taille de l'alphabet de la bande et du nombre d'états dans la MT. Le seul domino dont la taille peut être grande est le domino initial, qui aw $M$$w$$w$écrit dessus. Si nous généralisons cette réduction du travail sur les MT déterministes au travail sur les MT non déterministes, cela introduit au plus un certain nombre constant de dominos, car le nombre de transitions est fini. Par conséquent, nous pouvons construire l'ensemble standard de dominos pour la réduction normale de l'indécidabilité en temps polynomial.

Compte tenu de cela, nous pouvons réduire tout problème NP en BPCP comme suit - étant donné tout problème NP, il a un NTM à temps polynomial qui s'exécute dans le temps . Nous pouvons ensuite réduire ce problème à BPCP en temps polynomial comme suit - construire l'ensemble standard de dominos à partir de , puis demander s'il existe une solution qui utilise dominos, où est une fonction polynomiale qui exprime la nombre de dominos nécessaires pour que la solution existe (c'est probablement quelque chose comme , et ce n'est certainement pas exponentiel). Ensuite, en utilisant la même preuve que vous utilisez pour montrer que PCP est indécidable, vous pouvez prouver qu'il existe une solution à cette instance BPCP qui utilise au plus$M$$p(n)$$M$$f(p(n))$n 2 f ( p ( n ) ) M m p ( n $f$$n^2$$f(p(n))$si le NTM accepte dans les étapes . Par conséquent, nous avons une réduction du temps polynomial de chaque problème de NP à BPCP, donc BPCP est NP-difficile.$M$$m$$p(n)$

(Nous devons également montrer que BPCP est en NP, mais c'est facile; il suffit de deviner de manière non déterministe quels dominos mettre en ordre, puis de le vérifier de manière déterministe).

J'espère que cela t'aides!