Problemas de decisión frente a problemas "reales" que no son sí o no

36

Leí en muchos lugares que algunos problemas son difíciles de aproximar (es NP-difícil aproximarlos ). Pero la aproximación no es un problema de decisión: la respuesta es un número real y no Sí o No. Además, para cada factor de aproximación deseado, hay muchas respuestas correctas y muchas incorrectas, ¡y esto cambia con el factor de aproximación deseado!

Entonces, ¿cómo se puede decir que este problema es NP-hard?

(inspirado en la segunda viñeta en ¿Qué tan difícil es contar el número de rutas simples entre dos nodos en un gráfico dirigido? )

Sonó.
fuente

Respuestas:

27

Como dijiste, no hay que tomar una decisión, por lo que se necesitan nuevas clases de complejidad y nuevos tipos de reducciones para llegar a una definición adecuada de dureza NP para problemas de optimización .

Una forma de hacerlo es tener dos nuevas clases NPO y PO que contengan problemas de optimización y, por supuesto, imitan las clases NP y P para problemas de decisión. También se necesitan nuevas reducciones. Entonces podemos recrear una versión de dureza NP para problemas de optimización en la línea que fue exitosa para problemas de decisión. Pero primero tenemos que acordar qué es un problema de optimización .

Definición: Sea O = ( X , L , f , o p t )O=(X,L,f,opt) un problema de optimización . XX es el conjunto de entradas o instancias adecuadas codificadas como cadenas. LL es una función que asigna cada instancia x XxX a un conjunto de cadenas, las soluciones factibles de la instancia xx . Es un conjunto porque hay muchas soluciones para un problema de optimización. Por lo tanto, tenemos una función objetivo ff que nos dice para cada par (x , y ) (x,y) y L ( x )yL(x) de instancia y solución sucostoovalor. o p topt nos dice si estamos maximizando o minimizando.

Esto nos permite definir qué es una solución óptima : Sea y o p tL ( x )yoptL(x) la solución óptima de una instancia x XxX de un problema de optimización O = ( X , L , f , o p t )O=(X,L,f,opt) con f ( x , y o p t ) = o p t { f ( x , y)yL(x)}.

f(x,yopt)=opt{f(x,y)yL(x)}.
The optimal solution is often denoted by yy.

Now we can define the class NPO: Let NPONPO be the set of all optimization-problems O=(X,L,f,opt)O=(X,L,f,opt) with:

  1. XPXP
  2. There is a polynomial pp with |y|p(|x|)|y|p(|x|) for all instances xXxX and all feasible solutions yL(x)yL(x). Furthermore there is an deterministic algorithm that decides in polynomial time whether yL(x)yL(x).
  3. ff can be evaluated in polynomial time.

The intuition behind it is:

  1. We can verify efficiently if xx is actually a valid instance of our optimization problem.
  2. The size of the feasible solutions is bounded polynomially in the size of the inputs, And we can verify efficiently if yL(x)yL(x) is a fesible solution of the instance xx.
  3. The value of a solution yL(x)yL(x) can be determined efficiently.

This mirrors how NPNP is defined, now for PO: Let POPO be the set of all problems from NPONPO that can be solved by an deterministic algorithm in polynomial time.

Now we are able to define what we want to call an approximation-algorithm: An approximation-algorithm of an optimization-problem O=(X,L,f,opt)O=(X,L,f,opt) is an algorithm that computes a feasible solution yL(x)yL(x) for an instance xXxX.

Note: That we don’t ask for an optimal solution we only what to have a feasible one.

Now we have two types of errors: The absolute error of a feasible solution yL(x)yL(x) of an instance xXxX of the optimization-problem O=(X,L,f,opt)O=(X,L,f,opt) is |f(x,y)f(x,y)||f(x,y)f(x,y)|.

We call the absolute error of an approximation-algorithm AA for the optimization-problem OO bounded by kk if the algorithm AA computes for every instance xXxX a feasible solution with an absolute error bounded by kk.

Example: According to the Theorem of Vizing the chromatic index of a graph (the number of colours in the edge coloring with the fewest number of colors used) is either ΔΔ or Δ+1Δ+1, where ΔΔ is the maximal node degree. From the proof of the theorem an approximation-algorithm can be devised that computes an edge coloring with Δ+1Δ+1 colours. Accordingly we have an approximation-algorithm for the MinimumEdgeColoringMinimumEdgeColoring-Problem where the absolute error is bounded by 11.

This example is an exception, small absolute errors are rare, thus we define the relative error ϵA(x)ϵA(x) of the approximation-algorithm AA on instance xx of the optimization-problem O=(X,L,f,opt)O=(X,L,f,opt) with f(x,y)>0f(x,y)>0 for all xXxX and yL(x)yL(x) to be

ϵA(x):={0f(x,A(x))=f(x,y)|f(x,A(x))f(x,y)|max{f(x,A(x)),f(x,y)}f(x,A(x))f(x,y)

ϵA(x):={0|f(x,A(x))f(x,y)|max{f(x,A(x)),f(x,y)}f(x,A(x))=f(x,y)f(x,A(x))f(x,y)

where A(x)=yL(x)A(x)=yL(x) is the feasible solution computed by the approximation-algorithm AA.

We can now define approximation-algorithm AA for the optimization-problem O=(X,L,f,opt)O=(X,L,f,opt) to be a δδ-approximation-algorithm for OO if the relative error ϵA(x)ϵA(x) is bounded by δ0δ0 for every instance xXxX, thus ϵA(x)δxX.

ϵA(x)δxX.

The choice of max{f(x,A(x)),f(x,y)}max{f(x,A(x)),f(x,y)} in the denominator of the definition of the relative error was selected to make the definition symmetric for maximizing and minimizing. The value of the relative error ϵA(x)[0,1]ϵA(x)[0,1]. In case of a maximizing problem the value of the solution is never less than (1ϵA(x))f(x,y)(1ϵA(x))f(x,y) and never larger than 1/(1ϵA(x))f(x,y)1/(1ϵA(x))f(x,y) for a minimizing problem.

Now we can call an optimization-problem δδ-approximable if there is a δδ-approximation-algorithm AA for OO that runs in polynomial time.

We do not want to look at the error for every instance xx, we look only at the worst-case. Thus we define ϵA(n)ϵA(n), the maximal relativ error of the approximation-algorithm AA for the optimization-problem OO to be ϵA(n)=sup{ϵA(x)|x|n}.

ϵA(n)=sup{ϵA(x)|x|n}.

Where |x||x| should be the size of the instance.

Example: A maximal matching in a graph can be transformed in to a minimal node cover CC by adding all incident nodes from the matching to the vertex cover. Thus 1/2|C|1/2|C| edges are covered. As each vertex cover including the optimal one must have one of the nodes of each covered edge, otherwise it could be improved, we have 1/2|C|f(x,y)1/2|C|f(x,y). It follows that |C|f(x,y)|C|12

|C|f(x,y)|C|12
Thus the greedy algorithm for a maximal matching is a 1/21/2-approximatio-algorithm for MinimalVertexCoverMinimalVertexCover. Hence MinimalVertexCoverMinimalVertexCover is 1/21/2-approximable.

Unfortunately the relative error is not always the best notion of quality for an approximation as the following example demonstrates:

Example: A simple greedy-algorithm can approximate MinimumSetCoverMinimumSetCover. An analysis shows that |C||C|Hn1+ln(n)

|C||C|Hn1+ln(n)
and thus MinimumSetCoverMinimumSetCover would be ln(n)1+ln(n)ln(n)1+ln(n)-approximable.

If the relative error is close to 11 the following definition is advantageous.

Let O=(X,L,f,opt)O=(X,L,f,opt) be an optimization-problem with f(x,y)>0f(x,y)>0 for all xXxX and yL(x)yL(x) and AA an approximation-algorithm for OO. The approximation-ratio rA(x)rA(x) of feasible solution A(x)=yL(x)A(x)=yL(x) of the instance xXxX is rA(x)={1f(x,A(x))=f(x,y)max{f(x,A(x))f(x,y),f(x,y)f(x,A(x))}f(x,A(x))f(x,y)

rA(x)={1max{f(x,A(x))f(x,y),f(x,y)f(x,A(x))}f(x,A(x))=f(x,y)f(x,A(x))f(x,y)

As before we call an approximation-algorithm AA an rr-approximation-algorithm for the optimization-problem OO if the approximation-ratio rA(x)rA(x) is bounded by r1r1 for every input xXxX. rA(x)r

rA(x)r
And yet again if we have an rr-approximation-algorithm AA for the optimization-problem OO then OO is called rr-approximable. Again we only care about to the worst-case and define the maximal approximation-ratio rA(n)rA(n) to be rA(n)=sup{rA(x)|x|n}.
rA(n)=sup{rA(x)|x|n}.
Accordingly the approximation-ratio is larger than 11 for suboptimal solutions. Thus better solutions have smaller ratios. For MinimumSetCoverMinimumSetCover we can now write that it is (1+ln(n))(1+ln(n))-approximable. And in case of MinimumVertexCoverMinimumVertexCover we know from the previous example that it is 22-approximable. Between relative error and approximation-ratio we have simple relations: rA(x)=11ϵA(x)ϵA(x)=11rA(x).
rA(x)=11ϵA(x)ϵA(x)=11rA(x).

For small deviations from the optimum ϵ<1/2ϵ<1/2 and r<2r<2 the relative error is advantageous over the approximation-ratio, that shows its strengths for large deviations ϵ1/2ϵ1/2 and r2r2.

The two versions of αα-approximable don’t overlap as one version has always α1α1 and the other α1α1. The case α=1α=1 is not problematic as this is only reached by algorithms that produce an exact solution and consequentially need not be treated as approximation-algorithms.

Another class appears often APX. It is define as the set of all optimization-problems OO from NPONPO that haven an rr-approximation-algorithm with r1r1 that runs in polynomial time.

We are almost through. We would like to copy the successful ideas of reductions and completness from complexity theory. The observation is that many NP-hard decision variants of optimization-problems are reducible to each other while their optimization variants have different properties regarding their approximability. This is due to the polynomialtime-Karp-reduction used in NP-completness reductions, which does not preserve the objective function. And even if the objective functions is preserved the polynomialtime-Karp-reduction may change the quality of the solution.

What we need is a stronger version of the reduction, which not only maps instances from optimization-problem O1O1 to instances of O2O2, but also good solutions from O2O2 back to good solutions from O1O1.

Hence we define the approximation-preserving-reduction for two optimization-problems O1=(X1,L1,f1,opt1)O1=(X1,L1,f1,opt1) and O2=(X2,L2,f2,opt2)O2=(X2,L2,f2,opt2) from NPONPO. We call O1O1 APAP-reducible to O2O2, written as O1APO2O1APO2, if there are two functions gg and hh and a constant cc with:

  1. g(x1,r)X2g(x1,r)X2 for all x1X1x1X1 and rational r>1r>1
  2. L2(g(x,r1))L2(g(x,r1)) if L1(x1)L1(x1) for all x1X1x1X1 and rational r>1r>1
  3. h(x1,y2,r)L1(x1)h(x1,y2,r)L1(x1) for all x1X1x1X1 and rational r>1r>1 and for all y2L2(g(x1,r))y2L2(g(x1,r))
  4. For fixed rr both functions gg and hh can be computed by two algorithms in polynomial time in the length of their inputs.
  5. We have f2(g(x1,r),y2)rf1(x1,h(x1,y2,r))1+c(r1)
    f2(g(x1,r),y2)rf1(x1,h(x1,y2,r))1+c(r1)
    for all x1X1x1X1 and rational r>1r>1 and for all y2L2(g(x1,r))y2L2(g(x1,r))

In this definition gg and hh depend on the quality of the solution rr. Thus for different qualities the functions can differ. This generality is not always needed and we just work with g(x1)g(x1) and h(x1,y2)h(x1,y2).

Now that we have a notion of a reduction for optimization-problems we finally can transfer many things we know from complexity theory. For example if we know that O2APXO2APX and we show that O1APO2O1APO2 it follows that O1APXO1APX too.

Finally we can define what we mean by CC-hard and CC-complete for optimization-problems:

Let OO be an optimization-problem from NPONPO and CC a class of optimization-problems from NPONPO then OO is called CC-hard with respect to APAP if for all OCOC OAPOOAPO holds.

Thus once more we have a notion of a hardest problem in the class. Not surprising a CC-hard problem is called CC-complete with respect to APAP if it is an element of CC.

Thus we can now talk about NPONPO-completness and APXAPX-completness etc. And of course we are now asked to exhibit a first NPONPO-complete problem that takes over the role of SATSAT. It comes almost naturally, that WeightedSatisfiability can be shown to be NPO-complete. With the help of the PCP-Theorem one can even show that Maximum3SAT is APX-complete.

uli
fuente
11
Oh and please accept my apology for this comparatively long posting, but I didn't have time to write a shorter one.
uli
1
the punch line of course is that by the PCP theorem you can link MAX3SAT and SAT, thus showing that it's NP-hard to approximate MAX 3SAT to better than some constant. That is the equivalent of the Cook-Levin theorem, in a sense.
Suresh
1
@Suresh Of course, but this result you mention needs a gap-preserving reduction as far as I remember. And as you have already written about them in your post, I didn’t want to duplicate them here.
uli
Great answer, +1! I wonder if your answer is based on some references?
Tim
@Tim Of course there are books, I listed a few in the comments of another answer
uli
19

Usually what's shown is the NP-hardness of a "Gap" version of the problem. For example, suppose that you want to show that it's hard to approximate SET COVER to within a factor of 2.

You define the following "promise" instance of SET COVER that we'll call 2-GAP-SET-COVER:

Fix some number . 2-GAP-SET-COVER consists of all instances of set cover where the size of the optimal set cover is either:

  • at most
  • at least 2

Suppose we show that the problem of deciding which of the two cases a problem falls into is NP-complete. Then we've shown that approximating SET COVER to within a factor of 2 is NP-hard, because we could use such an algorithm to distinguish these two cases.

Suresh
fuente
4

The two existing answers are very informative but I don't think either of them really answers the question, which is, "How can a problem that isn't even a decision problem be NP-hard, when NP is a class of decision problems?"

The answer is to remember what NP-hard means. A problem L is NP-hard under some kind of reductions if every problem in NP can be reduced to L. (And L is NP-complete if it's NP-hard and in NP.) Informally, NP-hard means "If I could solve this problem, I could solve everything in NP", even if the problem you're talking about isn't in NP. NP-hardness does not require membership of NP, but it does need the right notion of reduction.

Some examples.

  1. Any NEXPTIME-complete problem L is NP-hard under polynomial-time many-one reductions. Any problem in NP is in NEXPTIME so is reducible to L by definition. By the time hierarchy theorem, L cannot be in NP, so L  is not NP-complete.
  2. #SAT is the problem of computing the number of satisfying assignments to CNF formulas. It is clearly not in NP because, as you observe, NP is a class of decision problems and #SAT is not one of those. However, #SAT is NP-hard under polynomial-time Turing reductions because we can reduce SAT to it. Given a SAT instance, we ask how many satisfying assignments there are: if there is at least one, we say "satisfiable"; otherwise, "unsatisfiable".
  3. Let APPROXSAT be the problem of computing a number which is within a factor of ten of the number of satisfying assignments to a CNF formula φ. Just to be annoying, let's say you're allowed to round down so, if φ has, say, three satisfying assignments, the algorithm is allowed to think "0.3" and round that down to zero. This is NP-hard under polynomial-time Turing reductions because we can still reduce SAT to it. Given a CNF formula φ, ask for the number of satisfying assignments to φ=φ(Z1Z10), where the Zi are new variables. φ is satisfiable if, and only if, φ is, but φ is guaranteed to have more than 1,000 satisfying assignments, if it has any. So, φ is satisfiable if, and only if, the APPROXSAT algorithm says that φ has at least 100 satisfying assignments.
David Richerby
fuente