Revision as of 22:21, 21 April 2023 edit David Eppstein (talk \| contribs) Autopatrolled, Administrators 235,647 edits Benny Chor ← Previous edit		Revision as of 21:56, 20 June 2024 edit undo Ben Standeven (talk \| contribs) Extended confirmed users, Pending changes reviewers 5,457 edits →DistNP-complete problems: specify distribution. Next edit →
Line 60: The average-case analogue to {{math\|'''NP'''}}-completeness is {{math\|'''distNP'''}}-completeness. A distributional problem {{math\|(''L′'', ''D′'')}} is {{math\|'''distNP'''}}-complete if {{math\|(''L′'', ''D′'')}} is in {{math\|'''distNP'''}} and for every {{math\|(''L'', ''D'')}} in {{math\|'''distNP'''}}, {{math\|(''L'', ''D'')}} is average-case reducible to {{math\|(''L′'', ''D′'')}}.<ref name="ab09" /> An example of a {{math\|'''distNP'''}}-complete problem is the Bounded Halting Problem, {{math\|({{mvar\|BH}},''D'')}} (for any P-computable ''D'') defined as follows: <math>BH = \{(M, x, 1^t) : M \text{ is a non-deterministic Turing machine that accepts } x \text{ in} \leq t \text{ steps}\}</math><ref name="ab09"/>

Average-case complexity: Difference between revisions