Tom@tanavit @HydrePrever @pyviv
Un problème de grand intérêt en théorie de la complexité et aussi en pratique. On se donne un circuit électronique fait à partir de "porte logique" avec plusieurs entrées (interrupteurs, 0 et 1) et une sortie. On veut savoir si on peut, en branchant une led sur la sortie, allumer la LED en bidouillant les interrupteurs …
C'est d'intérêt pratique, un microprocesseur par exemple c'est un gros circuit de cette nature (en partie), c'est d'intérêt théorique, c'est le premier problème démontré "NP-complet", et on peut formuler pleins de problème sous cette forme. Il y a des logiciels qui sont assez performants actuellement …/…
Un problème de grand intérêt en théorie de la complexité et aussi en pratique. On se donne un circuit électronique fait à partir de "porte logique" avec plusieurs entrées (interrupteurs, 0 et 1) et une sortie. On veut savoir si on peut, en branchant une led sur la sortie, allumer la LED en bidouillant les interrupteurs …
C'est d'intérêt pratique, un microprocesseur par exemple c'est un gros circuit de cette nature (en partie), c'est d'intérêt théorique, c'est le premier problème démontré "NP-complet", et on peut formuler pleins de problème sous cette forme. Il y a des logiciels qui sont assez performants actuellement …/…