#acl EditorsGroup:read,write,revert,admin MarioAlviano:read,write All:read

= Strategic Companies =


== 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 Oi is a subset of C', the associated company ci 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
 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.

The goal of the problem is a follows: Given two distinct companies c,,i,,,c,,j,, in C, we ask for checking whether no strategic set C' containing both c,,i,, and c,,j,, does exist.  Queries of this benchmark have thus to be answered cautiously.


== Predicates ==

 * '''Input''': {{{produced_by/5, controlled_by/5, strategic_pair/2, non_strategic_pair/2}}}

 * '''Output''': {{{yes}}} or {{{no}}} (meant as the propositional assertions {{{yes.}}} and {{{no.}}})

== 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 c,,1,,, c,,2,,, c,,3,, and c,,4,,;

 - 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 c,,1,,, c,,2,,, c,,3,, and c,,4,,;

 - A ground query of the form {{{non_strategic_pair(c1,c2)?}}}, specifying the query goal, i.e., whether no strategic set containing both c,,1,, and c,,2,, does exist.

For instance:
{{{
produced_by(pasta,barilla,dececco,dececco,dececco).
produced_by(tonno,callipo,star,star,star).
controlled_by(barilla,star,star,star,star).
controlled_by(dececco,barilla,barilla,barilla,barilla).
non_strategic_pair(barilla,star)?
}}}


== Output format ==
The output must be {{{yes.}}} or {{{no.}}} intended as {{{0}}}-ary facts. See the specification for outputs of query problems,  [[https://www.mat.unical.it/aspcomp2013/files/aspoutput.txt|here]].

For instance:
{{{
no.
}}}



== Example(s) ==

Input: 
{{{
produced_by(pasta,barilla,dececco,dececco,dececco).
produced_by(tonno,callipo,star,star,star).
controlled_by(barilla,star,star,star,star).
controlled_by(dececco,barilla,barilla,barilla,barilla).
non_strategic_pair(barilla, callipo)?
}}}

Output: 
{{{
yes.
}}}

Additional sample instances: [[https://www.mat.unical.it/aspcomp2013/files/samples/strategic_companies-sample.zip|download]]

== Problem Peculiarities ==

'''Type''': search/Beyond-NP
'''Competition''': both M&S and System competition

This problem is challenging both from the modelling point of view (it is required the availability of constructs allowing an "\exist \forall" quantification over solutions, or some appropriate optimization construct), and from the computational point of view.


== Author(s) ==
 * Author:  Mario Alviano
   * Affiliation: University of Calabria, Italy
 * Original Authors: Marco Maratea, Francesco Ricca
   * Affiliation: University of Genova and University of Calabria, Italy