Prev: CRYPT32.DLL _CryptVerifyCertificateSignatureEx@32 _CryptMsgVerifyCountersignatureEncodedEx@40 _CryptEncodeObject@20 _CryptDecodeObject@28 _CryptEncodeObjectEx@28 _CryptDecodeObjectEx@32 _CryptFormatObject@36 _CryptQueryObject@44 _CryptInitOIDFunct
Next: uncountable set maps 1 to 1 to a countable set
From: MeM on 20 Apr 2010 06:20
Since no example is known of a problem which is stronglysimple and not
p-simple no application of theorem 4 can be provided which is
different from the application given at the end of theorem 3. As a
conclusion of this paragraph we may observe thatthe results provided
insofar have a twofold implication. Qn one side they can be used in
order to characterize the computational complexity of one problem with
respect to thegiven definitions, on the other side they establish
conditions on the type of reductions found among problems belonging to
different classes, such as those discussed at the end of theorem 2 and
theorem 3. As a further example we may observe in the case of the
reduction from PARTITION to MAX-CUT the existence of a much more
succint reduction than the one given by Karp is ensured bynoting the
first problem is strongly simple while the second is weakly rigid.

4. STRONG NP-COMPLETENESS AND ITS RELATION TO RIGIDITY

In the preceding paragraph we have seen in some cases the
characterization of a problem B is not fully approximable comes out of
the fact we can reduce an NP-complete combinatorial problem A into a
subset of B° in which the measure is bounded by a polynomial. Garey
and Johnson give another way of considering subsets of the set INPUT
of a problem to study the different characteristics of NPCO problems.
Their paper (1978) is an attempt to understand the different roles
that numbers play in NPCO problems. Let us first consider, for
example, the problem MAX-CUT that is awell-known NPCO problem. If we
restrict those graphs with unitary weights we obtain a seemingly
easier problem SIMPLE-MAX-COT, however, is still an NPCO problem.
Different is the case of the problem JOB-SEQUENCING-WITH-DEADLINES: it
has been shown to be NP-complete by Karp, but if we restrict to the
case when all weights are unitary then the problem is solvable in
O(nlgn). Moreover if the weights are at most k the problem is solvable
by a classicdynamic approach in time bounded by a polynomial in k
andin n (the number of jobs). Note a polynomial algorithm must solve
JOB-SEQUENCING-WITH-DEADLINES in time bounded bya polynomial in n and
in lgk. In order to formalize these observations Garey and Johnson
introduce another function of the input MAX : INPUT -* Z captures the
notion of the magnitude of the largest number occurring in the input.
For example given a weighted graph G, MAX(G) can be defined as the
value of the maximum weighted edge. The following definitions
formalize these concepts.

DEFINITION 8. A pseudo-polynomial algorithm is analgorithm on input x
runs in time bound by a poly-nomial in |x| and in MAX(x).

DEFINITION 9. An NPCO problem is a pseudopolynomial NPCO problem if
there is a pseudopolynomial algorithm solves it.

DEFINITION 10. Given a problem P let P denote the problem acquired by
restricting P to only those instances xin INPUT for which MAX(x) < q(|
x|)

DEFINITION 11. An NPCO problem P is HP-complete in the strong sense if
there exists a polynomial q such P is NP-complete. An example of
pseudopolynomial NPCO problem is JOB-SEQUENCING-WITH-DEADLINES
( Lawler and Moore (1969)) while MAX-CÜT is NP-complete in the strong
sense (it is sufficient to consider the costant polynomial q(x) =1 to
obtain SIMPLE-MAX-CUT). The two classes of pseudopolynomial NPCO
problems and of strong NP-complete problems are disjoint (obviously
unless P = NP).

The following proposition states the relationshipbetween strong NP-
completeness and full approximability.

PROPOSITIONS.

If P is NP-complete in the strong sense then it is not fully
approximable. Garey and Johnson give another result connects the two
concepts of pseudopolynomial and fully approximable

NPCO problem; for clarity sake, we give later as an immediate
consequence of Theorem 6. In many problems the optimal value of the
measure and the MAX of the input have the same size or it is possible
to establish a polynomial relation between them.

This suggests the idea of comparing some of the different concepts
introduced in the preceding paragraphs and in this one.

First of all we can prove the following:

FACT 1 . Let A be a pseudopolynomial optimization problem. If there
exists a polynomial q such for every x £ INPUT . MAX(x) <q(m (x)-
m(x) , |x| ) , then give < x,k >, it is possible to decide in
polynomial time if m (x) <_k or*m (x) > k.

By hypothesis there are no more than q(Max(x),|x|)+1 iterations of
steps 2 .

As A is p-simple each iteration ofstep 2 takes no more than
Q(¡x|,q(MAX(x),|x|)+1).

Therefore m (x) is computable in at most (q(MAX(x),]x|)+1)-Q(|
x|,q(MAX(x) , |x|)) .

QED

COROLLARY. (Garey and Johnson (1978)).

Let A be a fully approximable NPCO problem. If there exists a
polynomial q such for every x e INPUT^ (m (x)-m(x))<q(MAX(x),|x|) then
A is a pseudopolynomial NPCO problem.

PROOF.

Immediate from the previous theorem and the fact a fully approximable
problem is p-simple. QED

As the conditions of theorem 5 and Fact 1 are generally verified the
two concepts of pseudopolynomial problem and p-simple problem coincide
in many cases.

A natural question arises at this point: when the conditions of the
theorems are not verified which of the two approaches gives better
information about the complexity of approximate algorithms?

Let us define nn subject to I a.y.=b y^ = 0,1 j=1,2,...n

A natural definition of MAX(INPUTp1) can be the following MAX(x)
=max(c.,a.) and it is not hard to prove that P1 is j 3 3
pseudopolynomial (a classic dynamic approach solves it in 20(n
MAX(x))); however even the problem to obtain any approximate solution
is an NP-complete problem (Karp (1972)).

Therefore P1 is a pseudopolynomial NPCO problem is not(P1) Max I c.y
approximable.

Let us consider now: n y.(P2) TTC, Jj=1 ]subject to j | a.J<b , y. =
0,1 j=1,2,...n3 ~ ' "D

This problem is fully approximable and we conjecture it is not a
pseudopolynomial problem because the classical method of deriving a
pseudopolynomial algorithm from the dynamic programming approach does
not work.

Theorems 5 and 6 and the previous examples show that Paz and Moran's
approach has a wider application for two different reasons.

First their approach is straightforward and there is no need to
introduce the function MAX whose definition can be ambiguous in some
cases.

In addition we have proven the two approaches are equivalent under
restricted but reasonable hypotheses and we show when m (x) and MAX(x)
are not polynomially related the approach formulated by Paz and Moran
remains adequate to study the complexity of approximation schemes for
NPCO problems. Before finishing this paragraph we want to observe when
there is a polynomial relation between the value of the optimal
solution and the value of MAX , there is a strong connection between
the two concepts of strong NP-complete and weakly rigid.

THEOREM 6.

Let A be a strong NP-complete optimization problem. If there exists a
polynomial p such for every x S INPUT^ (m (x)-m(x) ) <p(MAX(x) , |x|)
then A is weakly rigid.

PROOF.

If A is NP-complete in the strong sense there must exist a polynomial
q such the following set.Q= {<x,k)|< x,k > £AC, MAX{x) <q( |x|) } is
NP-complete.

Let us consider now the set As Q 2 Q' in order to prove Q=Q' it is
sufficient.to prove is the empty set.

In fact given (x,k>, with k>m(x) +p(MAX (x) ,|x|), we have by
hypothesis k>m(x)+p(MAX(x),|x|)>m (x) and therefore <x,k > ^ A .

Let us consider now Clearly Q" is NP-complete and hence A is weakly
rigid.

QED

CONCLUSIONS

We show there exist close relations among different approaches to the
classification of NP-complete optimization problems, giving new
resultson the type of possible reductions among problems belonging to
different classes.

On the other side, it is proof, violating some conditions, comparisons
among different concepts do not hold any more.Therefore the results
are useful contributions for better understanding of properties of
NPCO problems.

To provide meaningful characterizations of NOCO problems it is
necessary to find the suitable level of abstraction.

Meami.org

--MMM
 | 
Pages: 1
Prev: CRYPT32.DLL _CryptVerifyCertificateSignatureEx@32 _CryptMsgVerifyCountersignatureEncodedEx@40 _CryptEncodeObject@20 _CryptDecodeObject@28 _CryptEncodeObjectEx@28 _CryptDecodeObjectEx@32 _CryptFormatObject@36 _CryptQueryObject@44 _CryptInitOIDFunct
Next: uncountable set maps 1 to 1 to a countable set