Revision as of 11:52, 20 January 2010 edit Ylloh (talk \| contribs) Extended confirmed users 913 edits Improved first paragraph, still not perfect. Copied some wording from computational complexity theory. ← Previous edit		Revision as of 21:23, 27 February 2010 edit undo R'n'B (talk \| contribs) Administrators 426,003 edits m Fix links to disambiguation page Function Next edit →
Line 1: '''Parameterized complexity''' is a branch of [[computational complexity theory]] in [[computer science]] that focuses on classifying [[computational problems]] according to their inherent difficulty with respect to ''multiple'' parameters of the input. In parameterized complexity, the complexity of a problem is measured as a [[Function (mathematics)\|function]] in two or more parameters of the input. This way, parameterized complexity achieves to classify [[NP-hard]] problems on a finer scale than this is possible in the classical setting, where the complexity of a problem is only measured by the number of bits in the input. The first systematic work on parameterized complexity was done by {{harvtxt\|Downey\|Fellows\|1999}}.

Parameterized complexity: Difference between revisions