Editing Parameterized complexity (section)

==== ''W''[''t''] ====
<math>W[t]</math> can be defined using the family of Weighted Weft-{{mvar|t}}-Depth-{{mvar|d}} SAT problems for <math>d\geq t</math>:
<math>W[t,d]</math> is the class of parameterized problems that fpt-reduce to this problem, and <math>W[t] = \bigcup_{d\geq t} W[t,d]</math>.

Here, '''Weighted Weft-{{mvar|t}}-Depth-{{mvar|d}} SAT''' is the following problem:

* Input: A Boolean formula of depth at most {{mvar|d}} and weft at most {{mvar|t}}, and a number {{mvar|k}}. The ''depth'' is the maximal number of gates on any path from the root to a leaf, and the ''weft'' is the maximal number of gates ''of fan-in at least three'' on any path from the root to a leaf.
* 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 |last1=Buss |first1=Jonathan F |last2=Islam |first2=Tarique |title=Simplifying the weft hierarchy |journal=[[Theoretical Computer Science (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:

* Input: A Boolean formula of depth at most {{mvar|t}} with an AND-gate on top, and a number {{mvar|k}}.
* Question: Does the formula have a satisfying assignment of Hamming weight exactly {{mvar|k}}?