Content deleted Content added
→W hierarchy: Standard definition of W[1] (*exactly* k 1s, not *at most* k 1s.) Also, kill a “wicked which”. |
→W[t]: Changed the problem to its standard definition, <ref>https://www.sciencedirect.com/science/article/pii/S0304397505006262</ref> (Simplifying the Weft Hierarchy, Buss and Islam) |
||
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
It can be shown that 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>
Line 64:
* 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
==== ''W''[''P''] ====
| |||