Titre original :
A Survey of Lower Bounds for Satisfiability and Related Problems
Contenu du livre :
La complétude NP est sans doute le concept le plus répandu de l'informatique, car il englobe la complexité informatique de milliers de problèmes importants issus de toutes les branches de la science et de l'ingénierie.
La question P versus NP est de savoir si ces problèmes peuvent être résolus en temps polynomial. Une réponse négative a été largement conjecturée depuis longtemps mais, jusqu'à récemment, aucune limite inférieure concrète n'était connue sur les modèles généraux de calcul.
La satisfiabilité est le problème qui consiste à déterminer si une formule booléenne donnée possède au moins une affectation satisfaisante. Il s'agit du premier problème dont on a démontré qu'il était NP-complet, et il est probablement le problème NP-complet le plus étudié, tant pour ses propriétés théoriques que pour ses applications dans la pratique. A Survey of Lower Bounds for Satisfiability and Related Problems passe en revue les limites inférieures récemment découvertes pour la complexité en temps et en espace de la satisfiabilité et des problèmes étroitement liés.
Il donne un aperçu des résultats les plus récents sur les modèles de calcul déterministes, aléatoires et quantiques généraux et présente les arguments sous-jacents dans un cadre unifié. A Survey of Lower Bounds for Satisfiability and Related Problems est une référence inestimable pour les professeurs et les étudiants qui font de la recherche en théorie de la complexité ou qui prévoient d'en faire.
Autres informations sur le livre :
| ISBN : | 9781601980847 |
| Auteur : | |
| Éditeur : | |
| Langue : | anglais |
| Reliure : | Broché |
Achat:
Actuellement disponible, en stock.
