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

1 Answer

Gap problems are examples of promise problems, which are really the three-valued logic analogs of languages: some elements are in the language, some elements are not, and for the rest, we don't care.

A promise problem is in P if there is a polynomial time algorithm that answers Yes on all Yes instances and No on all No instances; we don't care what it answers on the don't care instances.

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$$.

We can similarly define the analogs of many other properties of languages. Usually this is done in an ad-hoc basis. We definitely think of promise problems as single languages rather than as a class of languages.

• I am sorry if this is an inappropriate place to ask, but is there a translation of the term promise-problem in Hebrew? – Dean Gurvitz Dec 3 '18 at 9:59
• There must be one, but I’m not aware of it. – Yuval Filmus Dec 3 '18 at 10:01