| dbo:abstract
|
- The vast majority of positive results about computational problems are constructive proofs, i.e., a computational problem is proved to be solvable by showing an algorithm that solves it; a computational problem is shown to be in P (complexity) by showing an algorithm that solves it in time that is polynomial in the size of the input; etc. However, there are several non-constructive results, where an algorithm is proved to exist without showing the algorithm itself. Several techniques are used to provide such existence proofs. (en)
- A maioria dos resultados positivos sobre problemas computacionais são provas construtivas, i.e. , um problema computacional é provado pra ser solucionado a partir de um algoritmo que o resolve; um problema computacional mostra-se em P(complexidade) dado que a partir da sua entrada tenha um algoritmo que o resolve em tempo polinomial; etc. No entanto, existem vários resultados não- construtivos, onde a existência de um algoritmo é provada sem mostrar o algoritmo por si só. Várias técnicas são usadas para fornecer a existências dessas provas. (pt)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 8866 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdfs:comment
|
- The vast majority of positive results about computational problems are constructive proofs, i.e., a computational problem is proved to be solvable by showing an algorithm that solves it; a computational problem is shown to be in P (complexity) by showing an algorithm that solves it in time that is polynomial in the size of the input; etc. However, there are several non-constructive results, where an algorithm is proved to exist without showing the algorithm itself. Several techniques are used to provide such existence proofs. (en)
- A maioria dos resultados positivos sobre problemas computacionais são provas construtivas, i.e. , um problema computacional é provado pra ser solucionado a partir de um algoritmo que o resolve; um problema computacional mostra-se em P(complexidade) dado que a partir da sua entrada tenha um algoritmo que o resolve em tempo polinomial; etc. No entanto, existem vários resultados não- construtivos, onde a existência de um algoritmo é provada sem mostrar o algoritmo por si só. Várias técnicas são usadas para fornecer a existências dessas provas. (pt)
|
| rdfs:label
|
- Non-constructive algorithm existence proofs (en)
- Existência de Algoritmos com provas Não construtivas (pt)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
