| Property |
Value |
| dbo:abstract
|
- #P, prononcé sharp P (ou dièse-P) est la classe des fonctions qui comptent le nombre de certificats d'un problèmes de décision qui est dans la classe NP. La classe #P tient une place à part dans la théorie de la complexité, car ce n'est pas une classe de problèmes de décision mais une classe de fonctions de comptage de solutions. Une fonction f est dans #P s'il existe une machine de Turing non-déterministe M fonctionnant en temps polynomial telle que pour toute instance x, f(x) soit le nombre d'exécutions de M acceptant x comme mot d'entrée. (fr)
- #P, prononcé sharp P (ou dièse-P) est la classe des fonctions qui comptent le nombre de certificats d'un problèmes de décision qui est dans la classe NP. La classe #P tient une place à part dans la théorie de la complexité, car ce n'est pas une classe de problèmes de décision mais une classe de fonctions de comptage de solutions. Une fonction f est dans #P s'il existe une machine de Turing non-déterministe M fonctionnant en temps polynomial telle que pour toute instance x, f(x) soit le nombre d'exécutions de M acceptant x comme mot d'entrée. (fr)
|
| dbo:namedAfter
| |
| dbo:thumbnail
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 7065 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
|
- 1979 (xsd:integer)
- 1992 (xsd:integer)
- 2002 (xsd:integer)
|
| prop-fr:annéePremièreÉdition
| |
| prop-fr:fin
|
- Symbols#sharpp (fr)
- Symbols#sharpp (fr)
|
| prop-fr:fr
|
- Parity P (fr)
- Parity P (fr)
|
| prop-fr:isbn
| |
| prop-fr:lienAuteur
|
- David S. Johnson (fr)
- David S. Johnson (fr)
|
| prop-fr:nom
|
- Johnson (fr)
- Valiant (fr)
- Ogihara (fr)
- #P (fr)
- Hemaspaandra (fr)
- Johnson (fr)
- Valiant (fr)
- Ogihara (fr)
- #P (fr)
- Hemaspaandra (fr)
|
| prop-fr:numéroD'édition
| |
| prop-fr:passage
|
- 189 (xsd:integer)
- 286 (xsd:integer)
|
| prop-fr:prénom
|
- David S. (fr)
- Mitsunori (fr)
- Lane A. (fr)
- Leslie G. (fr)
- David S. (fr)
- Mitsunori (fr)
- Lane A. (fr)
- Leslie G. (fr)
|
| prop-fr:périodique
|
- Theor. Comput. Sci. (fr)
- Theor. Comput. Sci. (fr)
|
| prop-fr:texte
| |
| prop-fr:titre
|
- The Complexity of Computing the Permanent (fr)
- The Complexity of Computing the Permanent (fr)
|
| prop-fr:titreChapitre
|
- A catalog of complexity classes (fr)
- Annexe A10 : #P: Counting functions (fr)
- A catalog of complexity classes (fr)
- Annexe A10 : #P: Counting functions (fr)
|
| prop-fr:titreOuvrage
|
- Algorithms and complexity (fr)
- The complexity theory companion (fr)
- Algorithms and complexity (fr)
- The complexity theory companion (fr)
|
| prop-fr:trad
|
- Parity P (fr)
- Parity P (fr)
|
| prop-fr:volume
| |
| prop-fr:wikiPageUsesTemplate
| |
| prop-fr:éditeur
|
- Springer (fr)
- Elsivier (fr)
- Springer (fr)
- Elsivier (fr)
|
| dct:subject
| |
| rdfs:comment
|
- #P, prononcé sharp P (ou dièse-P) est la classe des fonctions qui comptent le nombre de certificats d'un problèmes de décision qui est dans la classe NP. La classe #P tient une place à part dans la théorie de la complexité, car ce n'est pas une classe de problèmes de décision mais une classe de fonctions de comptage de solutions. Une fonction f est dans #P s'il existe une machine de Turing non-déterministe M fonctionnant en temps polynomial telle que pour toute instance x, f(x) soit le nombre d'exécutions de M acceptant x comme mot d'entrée. (fr)
- #P, prononcé sharp P (ou dièse-P) est la classe des fonctions qui comptent le nombre de certificats d'un problèmes de décision qui est dans la classe NP. La classe #P tient une place à part dans la théorie de la complexité, car ce n'est pas une classe de problèmes de décision mais une classe de fonctions de comptage de solutions. Une fonction f est dans #P s'il existe une machine de Turing non-déterministe M fonctionnant en temps polynomial telle que pour toute instance x, f(x) soit le nombre d'exécutions de M acceptant x comme mot d'entrée. (fr)
|
| rdfs:label
|
- Numeral-P (es)
- Sharp-P (de)
- Sharp-P (fr)
- Sharp-P (it)
- Sharp-P (ja)
- Класс ♯P (ru)
- سلم P (نظرية التعقيد) (ar)
- ♯P (ca)
- ♯P (en)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:isPartOf
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
