|
Size: 3623
Comment:
|
Size: 3698
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 7: | Line 7: |
| Strategic companies is a well-known NP^NP-complete problem that has often been used for systems comparisons, and also in the previous ASP Competitions. | Strategic companies is a well-known NP^NP^-complete problem that has often been used for systems comparisons, and also in the previous ASP Competitions. |
| Line 11: | Line 11: |
| C = c_1, ..., c_m | C = c,,1,,, ..., c,,m,, |
| Line 13: | Line 13: |
| of companies is given, for some m>=1. Each company produces some goods in a set G, and each company c_i in C is possibly controlled by a set of owner companies O_i (where O_i is a subset of C, for each i=1,...,m). In this context, a set C' of companies (i.e., a subset of C) is a "strategic set" if it is minimal among all the sets satisfying the following conditions: | of companies is given, for some {{{m>=1}}}. Each company produces some goods in a set {{{G}}}, and each company c,,i,, in C is possibly controlled by a set of owner companies O,,i,, (where O,,i,, is a subset of C, for each i=1,...,m). In this context, a set C' of companies (i.e., a subset of C) is a "strategic set" if it is minimal among all the sets satisfying the following conditions: |
| Line 15: | Line 15: |
| - Companies in C' produce all goods in G; <<BR>> | * Companies in C' produce all goods in G; * If O,,i,, is a subset of C', the associated company c_i must belong to C'(for each i=1,...,m). <<BR>> |
| Line 17: | Line 18: |
| - If O_i is a subset of C', the associated company c_i must belong to C'(for each i=1,...,m). <<BR>> | In our setting, instances are subject to two additional restrictions: |
| Line 19: | Line 20: |
| In our setting, instances are subjected to two additional restrictions: | 1. each product is produced by at most four companies; and 1. each company is controlled by at most four companies. <<BR>> |
| Line 21: | Line 23: |
| 1. each product is produced by at most four companies; and <<BR>> | Under these restrictions the problem is still NP^NP^-complete. <<BR>> Instances of strategic companies are encoded by means of the predicates {{{produced_by}}} and {{{controlled_by}}}. In particular, there is a fact {{{producedBy(p,c1,c2,c3,c4)}}} when a product p is produced by companies {{{c1}}}, {{{c2}}}, {{{c3}}} and {{{c4}}}, and a fact {{{controlledBy(c,c1,c2,c3,c4)}}} when a company {{{c}}} is controlled by companies {{{c1}}}, {{{c2}}}, {{{c3}}} and {{{c4}}}. If a product {{{p}}} is produced by less than four companies (but at least one), the atom {{{produced_by(p,c_a,c_b,c_c,c_d)}}} contains repetitions of companies. For instance, {{{producedBy(p,c_a,c_b,c_c,c_c)}}} is used for representing that p is produced solely by c,,a,,, c,,b,, and c,,c,,. Analogously, if a company c is controlled by less than four companies. |
| Line 23: | Line 28: |
| 2. each company is controlled by at most four companies. <<BR>> Under these restrictions the problem is still NP^NP-complete. <<BR>> Instances of strategic companies are encoded by means of the predicates produced_by and controlled_by. In particular, there is a fact {{{producedBy(p,c1,c2,c3,c4)}}} when a product p is produced by companies c1, c2, c3 and c4, and a fact {{{controlledBy(c,c1,c2,c3,c4)}}} when a company c is controlled by companies c1, c2, c3 and c4. If a product p is produced by less than four companies (but at least one), the atom {{{produced_by(p,c_a,c_b,c_c,c_d)}}} contains repetitions of companies. For instance, {{{producedBy(p,c_a,c_b,c_c,c_c)}}} is used for representing that p is produced solely by c_a, c_b and c_c. Analogously, if a company c is controlled by less than four companies. Moreover, two distinct companies c_i,c_j in C are provided in input (by means of predicate query), and the existence of a strategic set C' such that c_i and c_j occur in C' has to be checked. |
The goal of the problem is a follows: given two distinct companies c,,i,,,c,,j,, in C, we ask for checking the existence of a strategic set C' such that c,,i,, and c,,j,, occur in C'. |
| Line 34: | Line 32: |
| * '''Input''': {{{produced_by/5, controlled_by/5}}} * '''Query''': {{{query/2}}} |
* '''Input''': {{{produced_by/5, controlled_by/5, strategic_pair/2}}} |
| Line 42: | Line 38: |
| An instance of STRATCOMP is modeled by the following facts that will be provided in the input file: | An instance of Strategic Companies is modeled by the following facts that will be provided in the input file: |
| Line 48: | Line 44: |
| - A ground query atom of the form {{{query(c1,c2)}}}, specifying the query goal: Do c1 and c2 belong to a (minimal) strategic set? | - A ground fact of the form {{{strategic_pair(c1,c2)}}}, specifying the query goal: is there a strategic set containing both c1 and c2? |
| Line 54: | Line 50: |
| query(callipo,barilla)? | strategic_pair(callipo,barilla). |
| Line 58: | Line 54: |
If the answer to the input query is positive (i.e., for query(c1,c2), c1 and c2 jointly belong to a minimal strategic set), the output must contain a number of ground atoms of the form {{{strategic(i)}}} (where "strategic(i)" stands for "company i is strategic") witnessing that c1 and c2 belong to a strategic set. |
For {{{strategic_pair(c1,c2)}}}, if c1 and c2 jointly belong to a minimal strategic set, the output must contain a number of ground atoms of the form {{{strategic(c_i)}}} (where "strategic(c_i)" stands for "company c_i is strategic") including witnessing that c1 and c2 belong to a strategic set. |
Strategic Companies
Contents
Problem Description
Strategic companies is a well-known NPNP-complete problem that has often been used for systems comparisons, and also in the previous ASP Competitions.
In the Strategic Companies problem, a collection
C = c1, ..., cm
of companies is given, for some m>=1. Each company produces some goods in a set G, and each company ci in C is possibly controlled by a set of owner companies Oi (where Oi is a subset of C, for each i=1,...,m). In this context, a set C' of companies (i.e., a subset of C) is a "strategic set" if it is minimal among all the sets satisfying the following conditions:
- Companies in C' produce all goods in G;
If Oi is a subset of C', the associated company c_i must belong to C'(for each i=1,...,m).
In our setting, instances are subject to two additional restrictions:
- each product is produced by at most four companies; and
each company is controlled by at most four companies.
Under these restrictions the problem is still NPNP-complete.
Instances of strategic companies are encoded by means of the predicates produced_by and controlled_by. In particular, there is a fact producedBy(p,c1,c2,c3,c4) when a product p is produced by companies c1, c2, c3 and c4, and a fact controlledBy(c,c1,c2,c3,c4) when a company c is controlled by companies c1, c2, c3 and c4. If a product p is produced by less than four companies (but at least one), the atom produced_by(p,c_a,c_b,c_c,c_d) contains repetitions of companies. For instance, producedBy(p,c_a,c_b,c_c,c_c) is used for representing that p is produced solely by ca, cb and cc. Analogously, if a company c is controlled by less than four companies.
The goal of the problem is a follows: given two distinct companies ci,cj in C, we ask for checking the existence of a strategic set C' such that ci and cj occur in C'.
Predicates
Input: produced_by/5, controlled_by/5, strategic_pair/2
Output: strategic/1
Input format
An instance of Strategic Companies is modeled by the following facts that will be provided in the input file:
- A set of facts of the form produced_by(p,c1,c2,c3,c4), where produced_by(p,c1,c2,c3,c4) means that product P is produced by companies c1, c2, c3 and c4;
- A set of facts of the form controlled_by(c,c1,c2,c3,c4), where controlled_by(c,c1,c2,c3,c4) means that company c is jointly controlled by c1, c2, c3 and c4;
- A ground fact of the form strategic_pair(c1,c2), specifying the query goal: is there a strategic set containing both c1 and c2?
For instance:
produced_by(pasta,barilla,amato,dececco,divella). produced_by(tonno,callipo,star,almera,asdomar). controlled_by(callipo,star,almera,asdomar,barilla). controlled_by(barilla,callipo,almera,dececco,star). strategic_pair(callipo,barilla).
Output format
For strategic_pair(c1,c2), if c1 and c2 jointly belong to a minimal strategic set, the output must contain a number of ground atoms of the form strategic(c_i) (where "strategic(c_i)" stands for "company c_i is strategic") including witnessing that c1 and c2 belong to a strategic set.
Example(s)
Author(s)
- Author: Mario Alviano
- Affiliation: University of Calabria, Italy
- Author: Marco Maratea
- Affiliation: University of Genova
- Author: Francesco Ricca
- Affiliation: University of Calabria, Italy