Si j'ai un ensemble d'équations booléennes de n bits, y a-t-il un moyen simple ou un algorithme d'obtenir un ensemble de complément? Par exemple, disons que j'ai un ensemble d'équations booléennes à 3 bits {110, 001}, y a-t-il un moyen facile d'obtenir un ensemble de complément sous U (permutation sur 3 bits) {000,010,011,100,101,111}?complément d'ensemble d'équation booléenne
Merci!
Exécuter sur tout U (de 0 à 2^x - 1 où x est le nombre de bits) et omettre ceux que vous avez déjà. Vous pouvez les convertir en nombres pour faire vérifier l'égalité plus rapidement.
Mais quand x est assez grand, l'algorithme est exponentiel? Y at-il un moyen de l'éviter, ou le problème est NPC? Je vous remercie! – Ang
@koko - Le problème se développe de façon exponentielle, mais il n'est pas NP-complet. Différents concepts – mbeckish
@koko ok, c'est exponentiel. Pour moi, cela ressemble à la méthode la plus rapide, parce que sinon comment obtenir ces éléments? Si vous aviez une très grande quantité de nombres (par exemple, tous les nombres ont 1 en un seul bit), vous pouvez les pré-analyser pour pouvoir sauter le nombre de cycles dans une boucle. – Andrey
SET[] = {6, 1}
for(i=0;i<N;i++) {
if(!exists(SET)) {
add(i, COMPLEMENT_SET)
}
}
N = 2^n-1 Quelque chose comme ça ...
Vous pouvez soustraire votre jeu de U.
Mon point clé est lorsque n est augmentation, l'algorithme semble exponentielle? – Ang
Le nombre d'éléments dans U croît exponentiellement avec n, ce qui signifie que le nombre d'éléments dans le complément augmentera de façon exponentielle. – mbeckish
Il n'y a pas moyen de contourner l'algorithme (tout algorithme pour ce problème) étant exponentiel dans 'n' (ou, de façon équivalente, linéaire dans' O (2^n) '), où' n' est le nombre de bits. – NPE