Revision as of 15:41, 6 February 2022 edit Llammakey (talk \| contribs) Autopatrolled, Extended confirmed users, Page movers, IP block exemptions 150,023 edits m →para-NP: fixed cite error ← Previous edit		Revision as of 15:42, 6 February 2022 edit undo Llammakey (talk \| contribs) Autopatrolled, Extended confirmed users, Page movers, IP block exemptions 150,023 edits m →W[t]: fixed cs1 error Next edit →
Line 60: * Question: Does the formula have a satisfying assignment of [[Hamming weight]] exactly {{mvar\|k}}? It can be shown that for <math>t\geq2</math> the problem Weighted {{mvar\|t}}-Normalize SAT is complete for <math>W[t]</math> under fpt-reductions.<ref>{{cite journal \|~~author~~last1=Buss, \|first1=Jonathan F, \|last2=Islam, \|first2=Tarique \|title=Simplifying the weft hierarchy \|journal=Theoretical Computer Science \|year=2006 \|volume=351 \|number=3 \|pages=303–313 \|doi=10.1016/j.tcs.2005.10.002\|doi-access=free }}</ref> Here, '''Weighted {{mvar\|t}}-Normalize SAT''' is the following problem:

Parameterized complexity: Difference between revisions