| dbo:abstract
|
- Στη θεωρία υπολογιστικής πολυπλοκότητας και τη θεωρία υπολογισιμότητας, ένα πρόβλημα απαρίθμησης είναι ένα είδος υπολογιστικού προβλήματος. Έστω ότι το R είναι ένα πρόβλημα αναζήτησης. Τότε το είναι η αντίστοιχη και το υποδηλώνει το αντίστοιχο πρόβλημα απαρίθμησης. Να σημειωθεί ότι το cR είναι ένα πρόβλημα αναζήτησης, ενώ το #R είναι ένα πρόβλημα απόφασης. Παρ' όλα αυτά, το cR μπορεί να αναχθεί κατάCook στο #R με τη χρήση δυαδικής αναζήτησης (ο λόγος που το #R ορίζεται με αυτό τον τρόπο, αντί να αποτελεί απλώς το γράφο του cR, είναι για να επιτραπεί αυτή ακριβώς η δυαδική αναζήτηση). (el)
- In computational complexity theory and computability theory, a counting problem is a type of computational problem. If R is a search problem then is the corresponding and denotes the corresponding decision problem. Note that cR is a search problem while #R is a decision problem, however cR can be C Cook-reduced to #R (for appropriate C) using a binary search (the reason #R is defined the way it is, rather than being the graph of cR, is to make this binary search possible). (en)
- En théorie de la complexité et en théorie de la calculabilité, un problème de comptage est un type particulier de problème algorithmique.Étant donné un problème algorithmique consistant à trouver une solution, on peut définir le problème de comptage associé, qui consiste à calculer le nombre de solutions. Des classes de complexité spécifiques existent pour les problèmes de comptage, dont la plus connue #P qui est l'analogue de la classe NP pour les problèmes de décision. (fr)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 1687 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:title
|
- counting complexity class (en)
- counting problem (en)
|
| dbp:urlname
|
- CountingComplexityClass (en)
- CountingProblem (en)
|
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- Στη θεωρία υπολογιστικής πολυπλοκότητας και τη θεωρία υπολογισιμότητας, ένα πρόβλημα απαρίθμησης είναι ένα είδος υπολογιστικού προβλήματος. Έστω ότι το R είναι ένα πρόβλημα αναζήτησης. Τότε το είναι η αντίστοιχη και το υποδηλώνει το αντίστοιχο πρόβλημα απαρίθμησης. Να σημειωθεί ότι το cR είναι ένα πρόβλημα αναζήτησης, ενώ το #R είναι ένα πρόβλημα απόφασης. Παρ' όλα αυτά, το cR μπορεί να αναχθεί κατάCook στο #R με τη χρήση δυαδικής αναζήτησης (ο λόγος που το #R ορίζεται με αυτό τον τρόπο, αντί να αποτελεί απλώς το γράφο του cR, είναι για να επιτραπεί αυτή ακριβώς η δυαδική αναζήτηση). (el)
- In computational complexity theory and computability theory, a counting problem is a type of computational problem. If R is a search problem then is the corresponding and denotes the corresponding decision problem. Note that cR is a search problem while #R is a decision problem, however cR can be C Cook-reduced to #R (for appropriate C) using a binary search (the reason #R is defined the way it is, rather than being the graph of cR, is to make this binary search possible). (en)
- En théorie de la complexité et en théorie de la calculabilité, un problème de comptage est un type particulier de problème algorithmique.Étant donné un problème algorithmique consistant à trouver une solution, on peut définir le problème de comptage associé, qui consiste à calculer le nombre de solutions. Des classes de complexité spécifiques existent pour les problèmes de comptage, dont la plus connue #P qui est l'analogue de la classe NP pour les problèmes de décision. (fr)
|
| rdfs:label
|
- Πρόβλημα απαρίθμησης (el)
- Counting problem (complexity) (en)
- Problème de comptage (fr)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
