Weak Parametrized Inapproximability Hypothesis (WPIH)
Revision as of 11:31, 15 February 2023 by Admin (talk | contribs) (Created page with "== Target Problem == Approximate 2-CSP == Description == There is some constant $\delta > 0$ such that given an instance $\varphi$ of 2-CSP on the Boolean hypercube graph $Q$ over alphabet of size $n$, it is W(1)-hard to distinguish == Implies the following Hypothesis == == Implied by the following Hypothesis == == Computation Model == == Proven? == No == Year == == References/Citation == ? CCC '22")
Target Problem
Description
There is some constant $\delta > 0$ such that given an instance $\varphi$ of 2-CSP on the Boolean hypercube graph $Q$ over alphabet of size $n$, it is W(1)-hard to distinguish
Implies the following Hypothesis
Implied by the following Hypothesis
Computation Model
Proven?
No
Year
References/Citation
? CCC '22