La complexité de l'opération de projection

[lynda souadih]

Bonjour,

j'ai un problème à comprendre cet notion de complexité exponentielle
de l'opération de projection; d'après ma compréhension, cela veux dire
que le temps de calcul de la projection d'un graphe sur un autre est
multiplié d'une façon exponentielle mais je ne sais  pas par rapport à
quoi, est ce que c'est par rapport au nombre de nœuds du graphes à
projeter ou par rapport au graphe sur lequel on fait la projection. Et
si on suppose que les graphes à projeter sont toujours très petits par
rapport au graphes sur lesquelles on fait la projection cela changera
t il la complexité de l'opération de projection?

Merci

---------------------------------------------------------------------
To unsubscribe, e-mail: cg-unsubscribe@...
For additional commands, e-mail: cg-help@...

[ML Mugnier]

Lynda,

Consider for instance the following brute-force algorithm for computing
whether there is a projection from G1 to G2: generate all possible
mappings (applications) from the concept nodes in G1 to the concept
nodes of G2, and check for each mapping if it is a projection; if yes
return true. If all tests have failed, return false. Checking whether a
given mapping is a projection can be done in polynomial time. In the
worst case, the number of generated mappings is exponential in the
number of concept nodes in G1.
One can do better  in practice by using  various techniques, such as
computing a priori the set of possible images for each node in G1, but
in the worse case the exponential is still here. This is in line with
the fact that projection checking is NP-complete (see Chein & Mugnier,
RIA 1992).
Now, if the size of G1 is small with respect to that of G2 (for instance
G1 is a query and G2 is a ste of facts), then you may assume that it
bounded by a constant. In that case, the brute force algorithm is
polynomial, since only the size of G2 is taken into account.
Thiscorresponds to the notion of data complexity in databases.

Furthermore, even if G1 is "as big as" G2, projection is polynomial is
G1 is a tree, or is decomposable into a tree.

In our recent book (Chein & Mugnier, Graph-based Knowledge
Representation: Computational Foundations of Conceptual Graphs, see
http://www.lirmm.fr/gbkrbook), there is a whole chapter devoted to
projection algorithms, and to how techniques coming from constraint
networks can be exploited (chapter 6). There is also another chapter on
polynomial cases for projection (chapter 7).


Marie-Laure

lynda souadih a écrit :

> Bonjour,
>
> j'ai un problème à comprendre cet notion de complexité exponentielle
> de l'opération de projection; d'après ma compréhension, cela veux dire
> que le temps de calcul de la projection d'un graphe sur un autre est
> multiplié d'une façon exponentielle mais je ne sais  pas par rapport à
> quoi, est ce que c'est par rapport au nombre de nœuds du graphes à
> projeter ou par rapport au graphe sur lequel on fait la projection. Et
> si on suppose que les graphes à projeter sont toujours très petits par
> rapport au graphes sur lesquelles on fait la projection cela changera
> t il la complexité de l'opération de projection?
>
> Merci
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: cg-unsubscribe@...
> For additional commands, e-mail: cg-help@...
>  

--
Marie-Laure Mugnier

LIRMM (CNRS and University of Montpellier)
http://www.lirmm.fr/~mugnier


---------------------------------------------------------------------
To unsubscribe, e-mail: cg-unsubscribe@...
For additional commands, e-mail: cg-help@...

[Heather D. Pfeiffer]

Lynda,

  I am sorry, but I do not read French, but given Marie-Laure's
  response, you might also want to look at my dissertation at
  http://www.cs.nmsu.edu/~hdp/PDF/dissertation.pdf

  I describe how the data structures used can effect the practical
  implementation speed of the reasoning operations projection and
  maximal join.

-Heather

ML Mugnier writes:
 > Lynda,
 >
 > Consider for instance the following brute-force algorithm for computing
 > whether there is a projection from G1 to G2: generate all possible
 > mappings (applications) from the concept nodes in G1 to the concept
 > nodes of G2, and check for each mapping if it is a projection; if yes
 > return true. If all tests have failed, return false. Checking whether a
 > given mapping is a projection can be done in polynomial time. In the
 > worst case, the number of generated mappings is exponential in the
 > number of concept nodes in G1.
 > One can do better  in practice by using  various techniques, such as
 > computing a priori the set of possible images for each node in G1, but
 > in the worse case the exponential is still here. This is in line with
 > the fact that projection checking is NP-complete (see Chein & Mugnier,
 > RIA 1992).
 > Now, if the size of G1 is small with respect to that of G2 (for instance
 > G1 is a query and G2 is a ste of facts), then you may assume that it
 > bounded by a constant. In that case, the brute force algorithm is
 > polynomial, since only the size of G2 is taken into account.
 > Thiscorresponds to the notion of data complexity in databases.
 >
 > Furthermore, even if G1 is "as big as" G2, projection is polynomial is
 > G1 is a tree, or is decomposable into a tree.
 >
 > In our recent book (Chein & Mugnier, Graph-based Knowledge
 > Representation: Computational Foundations of Conceptual Graphs, see
 > http://www.lirmm.fr/gbkrbook), there is a whole chapter devoted to
 > projection algorithms, and to how techniques coming from constraint
 > networks can be exploited (chapter 6). There is also another chapter on
 > polynomial cases for projection (chapter 7).
 >
 >
 > Marie-Laure
 >
 > lynda souadih a �Aicrit :
 > > Bonjour,
 > >
 > > j'ai un probl�Ahme �A` comprendre cet notion de complexit�Ai exponentielle
 > > de l'op�Airation de projection; d'apr�Ahs ma compr�Aihension, cela veux dire
 > > que le temps de calcul de la projection d'un graphe sur un autre est
 > > multipli�Ai d'une fa�Agon exponentielle mais je ne sais  pas par rapport �A`
 > > quoi, est ce que c'est par rapport au nombre de n�1 suds du graphes �A`
 > > projeter ou par rapport au graphe sur lequel on fait la projection. Et
 > > si on suppose que les graphes �A` projeter sont toujours tr�Ahs petits par
 > > rapport au graphes sur lesquelles on fait la projection cela changera
 > > t il la complexit�Ai de l'op�Airation de projection?
 > >
 > > Merci
 > >
 > > ---------------------------------------------------------------------
 > > To unsubscribe, e-mail: cg-unsubscribe@...
 > > For additional commands, e-mail: cg-help@...
 > >  
 >
 >
 > --
 > Marie-Laure Mugnier
 >
 > LIRMM (CNRS and University of Montpellier)
 > http://www.lirmm.fr/~mugnier
 >
 >
 > ---------------------------------------------------------------------
 > To unsubscribe, e-mail: cg-unsubscribe@...
 > For additional commands, e-mail: cg-help@...



---------------------------------------------------------------------
To unsubscribe, e-mail: cg-unsubscribe@...
For additional commands, e-mail: cg-help@...