Content deleted Content added
m fixed CS1 errors: dates to meet MOS:DATEFORMAT (also General fixes) using AWB (10083) |
m →''W''[''t'']: Journal cites, Added 1 doi to a journal cite using AWB (10365) |
||
Line 64:
* Question: Does the formula have a satisfying assignment of Hamming weight at most <math>k</math>?
It can be shown that the problem Weighted <math>t</math>-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| publisher=Elsevier| accessdate=16 April 2014| doi=10.1016/j.tcs.2005.10.002}}</ref>
Here, '''Weighted <math>t</math>-Normalize SAT''' is the following problem:
| |||