# Defining Gap Problems

I recently started studying about approximation problems in the complexity class that I'm taking. I feel like some of the definitions in this subject presented in my course and that I came across online are somewhat inaccurate and confusing.

Specifically, the concept of gap problems wasn't completely clear to me. It was presented to us that gap problems are a way to formulate decision problems from approximation problems. However, it seems to me that a gap problem isn't precisely a decision problem (or, let's say, a language), but rather a set of decision problems/languages that satisfy two common conditions.

For example, I would think that gap-$$IndependentSet[a,b]$$ could be defined as the set of all languages $$L$$ such that:

• If $$G=(V,E)$$ has an independent set of size $$>b$$ than necessarily $$G\in L$$
• If $$G=(V,E)$$ doesn't have an independent set of size $$>a$$ than necessarily $$G\notin L$$

If such a definition for a gap problem is valid, then I think two more definitions need clarification:

1. A gap-preserving-reduction isn't in fact a proper Karp reduction, because it doesn't map a single language to another language. Rather, it maps certain "good inputs" to other "good inputs" and "bad inputs" to other "bad inputs", without having any requirements about the rest of the inputs.

2. A gap problem cannot be an element of a complexity class (such as $$NP$$), but rather a subset of the class. In that case, saying that a certain gap problem is $$NP$$-complete would actually mean that all languages in the problem are $$NP$$-complete

Is this a valid way to think about the subject? Am I just confusing myself? Should I stick to the basic intuition and not try to define approximation related concepts in these terms?

• – Yuval Filmus Dec 3 '18 at 9:23

A promise problem $$L$$ is NP-hard if for every NP problem $$L'$$ there is a polytime reduction $$f$$ such that if $$x \in L'$$ then $$f(x)$$ is a Yes instance of $$L$$, and if $$x \notin L'$$ then $$f(x)$$ is a No instance of $$L$$.