What is inapproximability of NP-hard problems?
Optimization problems come in two flavors: minimization and maximization. For definiteness, in this answer we consider minimization problems; for maximization problems the situation is completely analogous.

Generally speaking, when we say that a minimization problem $\Pi$ is $c$-hard to approximate, we mean the following:


  If there is a polynomial time approximation algorithm for $\Pi$ whose approximation ratio is better than $c$ then [something bad happens].


Usually the "something bad" is $\mathsf{P} = \mathsf{NP}$, but sometimes we can only prove that, say $\mathsf{NP} \subseteq \mathsf{DTime}(n^{\log \log n})$ (that is, SAT can be solved in time $O(n^{
\log \log n})$). Since we believe that the "something bad" is wrong, it follows that probably no polynomial time approximation algorithm for $\Pi$ has an approximation ratio better than $c$.

Why this form of result? If $\mathsf{P} = \mathsf{NP}$, then all NP optimization problems (that is, all optimization problems whose decision version is in NP) can be solved in polynomial time. Therefore in order to prove that a certain problem cannot be approximated well we need to make some complexity assumption such as $\mathsf{P} \neq \mathsf{NP}$.

The best one can hope for is to prove that is an NP-hard to approximate $\Pi$ better than $c$. What this means is that for each $\epsilon &gt; 0$ there is a polynomial reduction $A$ from SAT to $\Pi$ with the following properties:


If the input formula $\varphi$ is satisfiable than the optimal value of $A(\varphi)$ is at most $x$, for some value $x$ which the reduction explicitly calculates (in polynomial time).
If $\varphi$ is not satisfiable than the optimal value of $A(\varphi)$ is more than $(c+\epsilon)x$.


In particular, any polynomial time $(c+\epsilon)$-approximation algorithm would be able to distinguish the two cases, and thus to solve SAT in polynomial time.

Technically, what we have described is known as a promise problem: decide whether an instance of $\Pi$ has value at most $x$ or more than $(c+\epsilon)x$; or stated differently, find the optimal value of an instance of $\Pi$ (or at least distinguish the two cases) under the promise that the optimal value is either at most $x$ or more than $(c+\epsilon)x$.

In some cases we are able to prove that a certain problem $\Pi$ is $c$-hard to approximate, and also show that a polynomial time $c$-approximation algorithm exists. In this case we say that the inapproximability threshold of $\Pi$ is $c$. For example, H&aring;stad shows that the threshold of inapproximability for 3SAT is $7/8$.

Our definition above of $c$-inapproximability states that in polynomial time it is impossible to approximate a certain problem better than $c$, but allows an approximation ratio of $c$. Sometimes we also want to disallow an approximation ratio of $c$. The terminology doesn't reflect this fine point, and formal statements of theorems have to be consulted.

Finally, $(1+\epsilon)$-inapproximability means that (under some complexity assumptions) it is impossible (in polynomial time) to approximate the problem to within $1+\epsilon$ for some $\epsilon &gt; 0$ (in terms of our notation above, the problem is $1$-hard to approximate). We also say that the problem is APX-hard.

Logarithmic inapproximability means that it is impossible to approximate the problem to within $O(\log n)$, where $n$ is some natural parameter inherent in the problem, usually the number of vertices in the input graph.