Content deleted Content added
GreenC bot (talk | contribs) Rescued 1 archive link. Wayback Medic 2.5 |
m link Hamming weight using Find link |
||
Line 58:
* 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 |author=Buss, Jonathan F, Islam, 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}}</ref>
| |||