Generic-case complexity

Generic-case complexity is a subfield of <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a> that studies the complexity of computational problems on "most inputs".
Generic-case complexity is a way of measuring the complexity of a <a href="/facts/Computational_problem/jQ7bYUVh">computational problem</a> by neglecting a small set of
unrepresentative inputs and considering <a href="/facts/Worst-case_complexity/kqzQkwIc">worst-case complexity</a> 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 <a href="/facts/Combinatorial_group_theory/dh5VHLga">combinatorial group theory</a>, 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 <a href="/facts/Finitely_generated_group/fVsFHrmb">finitely generated groups</a> the generic time complexity of some classical <a href="/facts/Decision_problems/cQNWjbdE">decision problems</a> from combinatorial group theory, namely the <a href="/facts/Word_problem_for_groups/eKBrkBPv">word problem</a>, <a href="/facts/Conjugacy_problem/E951lR5q">conjugacy problem</a> and membership problem, are linear.
A detailed introduction of generic case complexity can be found in the surveys.

Generic-case complexity open-in-new

Generic-case complexity