This HTML5 document contains 75 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n14https://global.dbpedia.org/id/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
dbpedia-pthttp://pt.dbpedia.org/resource/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
dbpedia-frhttp://fr.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
provhttp://www.w3.org/ns/prov#
dbphttp://dbpedia.org/property/
dbchttp://dbpedia.org/resource/Category:
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
goldhttp://purl.org/linguistics/gold/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Whitehead's_algorithm
dbo:wikiPageWikiLink
dbr:Generic-case_complexity
Subject Item
dbr:General_position
dbo:wikiPageWikiLink
dbr:Generic-case_complexity
Subject Item
dbr:Generic-case_complexity
rdf:type
dbo:Disease
rdfs:label
Complexidade de caso genérico Generic-case complexity Complexité générique des algorithmes
rdfs:comment
Complexidade de Caso Genérico é uma subárea da teoria da complexidade computacional que estuda a complexidade de problemas computacionais na "maioria das entradas". Complexidade de Caso Genérico é uma forma de medir a complexidade de um problema computacional desprezando um pequeno conjunto de entradas não representativas e aplicando a complexidade do pior caso nas entradas restantes.Pequeno é definido em termos de densidade assintótica.A aparente eficácia da complexidade de caso genérico se dá porque, para uma ampla variedade de problemas computacionais concretos, as instâncias mais difíceis parecem ser raras. Os casos típicos, são relativamente fáceis. Generic-case complexity is a subfield of computational complexity theory that studies the complexity of computational problems on "most inputs". Generic-case complexity is a way of measuring the complexity of a computational problem by neglecting a small set ofunrepresentative inputs and considering worst-case complexity on the rest.Small is defined in terms of asymptotic density.The apparent efficacy of generic case complexity is because for a wide variety of concrete computational problems, the most difficult instances seem to be rare. Typical instances are relatively easy. La complexité générique est un domaine particulier de la complexité algorithmique qui concerne l’étude de la complexité de problèmes algorithmiques pour « la plupart des données ». La complexité générique est une façon de mesurer la complexité d'un problème algorithmique en négligeant un petit ensemble d'entrées non représentatives et en considérant la complexité dans le pire des cas sur les entrées restantes. La concept de « petit ensemble » est définie en termes de densité asymptotique. L'efficacité apparente des algorithmes mesurée par leur complexité générique provient du fait que, pour une grande variété de problèmes informatiques concrets, les cas les plus difficiles semblent être rares, alors que les cas typiques sont, eux, relativement faciles.
dcterms:subject
dbc:Computational_complexity_theory
dbo:wikiPageID
24731030
dbo:wikiPageRevisionID
890164322
dbo:wikiPageWikiLink
dbr:Rice's_theorem dbr:Satisfiability_problem dbr:Stolz_theorem dbr:Probability_distribution dbr:Undecidable_problem dbr:Probability_distributions dbr:Worst-case_complexity dbr:Bounded_halting_problem dbr:Exponential_time dbr:Halting_problem dbr:Conjugacy_problem dbr:HNN_extension dbr:Turing_machine dbr:Formal_languages dbr:Subset_sum_problem dbc:Computational_complexity_theory dbr:Membership_problem dbr:Algorithm dbr:Finitely_generated_group dbr:One-way_function dbr:Anshel–Anshel–Goldfeld_key_exchange dbr:Average_case_complete_problems dbr:Braid_group dbr:Linear_time dbr:Average-case_complexity dbr:Infinite_set dbr:Time_complexity dbr:Decision_problems dbr:Computational_problem dbr:Search_problem dbr:Decision_problem dbr:Polynomial_time dbr:Word_problem_for_groups dbr:NP_complete dbr:Coset_enumeration dbr:Computational_complexity_theory dbr:Post_correspondence_problem dbr:Free_group dbr:P_=_NP dbr:Combinatorial_group_theory dbr:Presburger_arithmetic dbr:Length_based_attack dbr:NP-complete_problems
owl:sameAs
wikidata:Q5532647 freebase:m.080b9c_ n14:4kWzz dbpedia-pt:Complexidade_de_caso_genérico dbpedia-fr:Complexité_générique_des_algorithmes
dbp:wikiPageUsesTemplate
dbt:Reflist
dbo:abstract
Generic-case complexity is a subfield of computational complexity theory that studies the complexity of computational problems on "most inputs". Generic-case complexity is a way of measuring the complexity of a computational problem by neglecting a small set ofunrepresentative inputs and considering worst-case complexity on the rest.Small is defined in terms of asymptotic density.The apparent efficacy of generic case complexity is because for a wide variety of concrete computational problems, the most difficult instances seem to be rare. Typical instances are relatively easy. This approach to complexity originated in combinatorial group theory, which has a computational tradition going back to the beginning of the last century.The notion of generic complexity was introduced in a 2003 paper, where authors showed that for a large class of finitely generated groups the generic time complexity of some classical decision problems from combinatorial group theory, namely the word problem, conjugacy problem and , are linear. A detailed introduction of generic case complexity can be found in the surveys. Complexidade de Caso Genérico é uma subárea da teoria da complexidade computacional que estuda a complexidade de problemas computacionais na "maioria das entradas". Complexidade de Caso Genérico é uma forma de medir a complexidade de um problema computacional desprezando um pequeno conjunto de entradas não representativas e aplicando a complexidade do pior caso nas entradas restantes.Pequeno é definido em termos de densidade assintótica.A aparente eficácia da complexidade de caso genérico se dá porque, para uma ampla variedade de problemas computacionais concretos, as instâncias mais difíceis parecem ser raras. Os casos típicos, são relativamente fáceis. Esta abordagem da complexidade foi originada em teoria combinatória dos grupos, que tem uma tradição computacional que remonta ao início do século passado.A noção de complexidade genérica foi introduzida em um artigo de 2003 onde os autores mostraram que, para uma grande classe de grupos gerados finitamente a complexidade de tempo genérica de alguns problemas clássicos de decisão provenientes da teoria combinatória dos grupos, conhecidamente, o problema da aceitação de uma palavra, problema da conjugação e o problema da pertinência, são lineares. Uma introdução detalhada da complexidade de caso genérico pode ser encontrado nas pesquisas. La complexité générique est un domaine particulier de la complexité algorithmique qui concerne l’étude de la complexité de problèmes algorithmiques pour « la plupart des données ». La complexité générique est une façon de mesurer la complexité d'un problème algorithmique en négligeant un petit ensemble d'entrées non représentatives et en considérant la complexité dans le pire des cas sur les entrées restantes. La concept de « petit ensemble » est définie en termes de densité asymptotique. L'efficacité apparente des algorithmes mesurée par leur complexité générique provient du fait que, pour une grande variété de problèmes informatiques concrets, les cas les plus difficiles semblent être rares, alors que les cas typiques sont, eux, relativement faciles. Cette approche de la complexité prend son origine dans la théorie combinatoire des groupes qui a une tradition dans l'étude de problèmes algorithmiques qui remonte au début du XXe siècle. La notion de complexité générique a été introduit en 2003 dans des articles de Kapovich, Miasnikov, Schupp et Shpilrain. Les auteurs montrent que, pour une large classe de groupes finiment engendrés, la complexité générique de quelques problèmes de décision classiques de la théorie combinatoire des groupes, à savoir le problème du mot, le (en), ou le problème d'appartenance, est en fait linéaire. Une introduction et un survol de la complexité générique sont donnés dans un texte de R. Gilman, A. G. Miasnikov, A. D. Myasnikov, et A. Ushakov. Les livres de Miasnikov, Shpilrain et Ushakov traitent principalement des résultats des auteurs relativement à la cryptographie.
gold:hypernym
dbr:Subfield
prov:wasDerivedFrom
wikipedia-en:Generic-case_complexity?oldid=890164322&ns=0
dbo:wikiPageLength
18108
foaf:isPrimaryTopicOf
wikipedia-en:Generic-case_complexity
Subject Item
dbr:Geometric_group_theory
dbo:wikiPageWikiLink
dbr:Generic-case_complexity
Subject Item
dbr:Baumslag–Gersten_group
dbo:wikiPageWikiLink
dbr:Generic-case_complexity
Subject Item
dbr:Joel_David_Hamkins
dbo:wikiPageWikiLink
dbr:Generic-case_complexity
Subject Item
dbr:Social_complexity
dbo:wikiPageWikiLink
dbr:Generic-case_complexity
Subject Item
dbr:Generic_case_complexity
dbo:wikiPageWikiLink
dbr:Generic-case_complexity
dbo:wikiPageRedirects
dbr:Generic-case_complexity
Subject Item
wikipedia-en:Generic-case_complexity
foaf:primaryTopic
dbr:Generic-case_complexity