= Strategic Companies =

<<TableOfContents>>

== Problem Description ==

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.

In the Strategic Companies problem, a collection 

  C = c,,1,,, ..., c,,m,,

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:

 * 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>>

In our setting, instances are subject 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>>

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.

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'.

== 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)}}} in input, 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") encoding the minimal strategic set which c1 and c2 belong to.

== Example(s) ==

== Notes ==

Note that this is a search problem, despite the seemingly presence of a ''query'' in input.

== 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