Parametrized Inapproximability Hypothesis (PIH)
Jump to navigation
Jump to search
Target Problem
Description
There is some constant $\delta > 0$ such that 2-CSP on $k$ vertices and alphabet size $n$ is W(1)-hard to approximate to a $(1-\delta)$ factor
Implies the following Hypothesis
Implied by the following Hypothesis
Computation Model
Proven?
No
Year
2017