|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Stanislav Shwartsman 2:400/520 12 Jul 2002 11:00:29
To : Alexander Shmidt
Subject : Типы NP-полных задач
--------------------------------------------------------------------------------
10 Jul 02 20:49, you wrote to All:
AS> Hасколько я слышал, есть всего семь общих сабжей. Одни из них: задача
AS> коммивояжера и поиск наименьшего гамильтонова пути (или она к ЗК
AS> сводится?). Какие еще есть типы?
NP-полных задач есть несколько сотен. Смотри на
http://www.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html
An Annotated List of Selected NP-complete Problems
Там перечисленно 88 проблем, вот первая десятка:
-------------------------------------------------------------------------------
Number: 1
Name: 3-Satisfiability (3-SAT) [LO2] 2
Input: A set of m clauses - C1 ,C2,...,Cm - over a set of n Boolean valued
variables Xn=< x1,x2,...,xn>, such that each clause depends on exactly three
distinct variables from Xn. A clause being a Boolean expression of the form
yi+yj+yk where each y is of the form x or -x (i.e. negation of x) with x being
some variable in Xn. For example if n=4 and m=3 a possible instance could be the
(set of) Boolean expressions: C1=(x1+(-x2)+(-x3)); C2=(x2+x3+(-x4));
C3=((-x1)+x3+x4);
Question: Can each variable xi of Xn be assigned a Boolean value alphai in such
a way that every clause evaluates to the Boolean result true under the
assignment < xi:=alphai:1<=i<=n>?
In the example instance, the assignment < x1:=true;x2:=false;x3:=true;
x4:=false> is such that each of the three clauses takes the value true.
Comments: For reasons that will become clearer at the end of the course, this
problem had to be Number 1. Some relevant material concerning this problem might
be found in the special issue (Volume 81, 1996) of the journal Artificial
Intelligence that is available in the Library.
-------------------------------------------------------------------------------
Number: 2
Name: Graph 3-Colourability (3-COL) [GT4] 1
Input: An n-node undirected graph G(V,E) with node set V and edge set E.
Question: Can each node of G(V,E) be assigned exactly one of three colours -
Red, Blue, Green - in such a way that no two nodes which are joined by an edge,
are assigned the same colour?
-------------------------------------------------------------------------------
Number: 3
Name: Monochromatic triangle [GT6] 2
Input: An n-node undirected graph G(V,E) with node set V and edge set E.
Question: Can the edges, E, of G be partitioned into two disjoint sets E1 and
E2, in such a way that neither of the two graphs G1(V,E1) or G2(V,E2) contains a
triangle, i.e. a set of three distinct nodes u,v,w such that {u,v}, {u,w}, {v,w}
are all edges?
-------------------------------------------------------------------------------
Number: 4
Name: Clique [GT19] 1
Input: An n-node undirected graph G(V,E) with node set V and edge set E; a
positive integer k with k<=n.
Question: Does G contain a k-clique, i.e. a subset W of the nodes V such that W
has size k and for each distinct pair of nodes u, v in W, {u,v} is an edge of G?
-------------------------------------------------------------------------------
Number: 5
Name: Bipartite Subgraph [GT25] 2
Input: An n-node undirected graph G(V,E) with node set V and edge set E; a
positive integer k with k<=|E|.
Question: Is there a subset, F of the edges of G, having size at least k and
such that the graph H(V,F) is bipartite?
Comments: G(V,E) is bipartite if the nodes can be partitioned into two disjoint
sets U and W such that every edge of G connects a node in U to a node in W, i.e.
no two nodes in U (resp. W) form an edge of G.
-------------------------------------------------------------------------------
Number: 6
Name: Vertex Cover [GT1] 1
Input: An n-node undirected graph G(V,E) with node set V and edge set E; a
positive integer k with k<=n.
Question: Is there a subset W of V having size at most k and such that for every
edge {u,v} in E at least one of u and v belongs to W?
-------------------------------------------------------------------------------
Number: 7
Name: Chromatic Index (Edge Colouring) [OPEN5] 3
Input: An n-node undirected graph G(V,E) with node set V and edge set E; a
positive integer k with k<=|E|.
Question: Can the edges of G be assigned exactly one of k colours in such a way
that no two edges which have a common node as an endpoint are assigned the same
colour?
Comments: Vizing's Theorem from Graph Theory shows that the only `hard' case for
this problem is when k is equal to the maximum degree of G. The degree of a
node, v, is the number of edges in the graph with v as an end-point; the degree
of a graph is the maximum degree of any node in the graph. Chromatic Index was
shown to be NP-complete soon after the 1979 edition of Garey and Johnson went to
press, hence the OPEN categorisation.
The classical paper on sequential methods is:
A.M. Gibbons and O.A. Ogunyode: Optimal edge-colouring of almost all simple
graphs in polynomial time. Random Graphs `85: Conf. Record of 2nd International
Seminar on Random Graphs and Probabilistic Methods in Combinatorics, Poznan,
North-Holland, (1985).
There are also a number of methods presenting efficient parallel algorithms for
various special types of graph. Some of the ideas presented in these may be
useful in formulating sequential techniques, e.g.
A.M. Gibbons and W. Rytter: Optimally edge-colouring outerplanar graphs is in
NC. Theoretical Computer Science, 71, (1990), pp. 401-411
A.M. Gibbons and W. Rytter: Fast parallel algorithms for optimal edge-colouring
of some tree-structured graphs. Fundamentals of Computation Theory (FCT) `87,
Springer-Verlag, 1987
-------------------------------------------------------------------------------
Number: 8
Name: Multiprocessor Scheduling [SS8] 4
Input: A set, T, of tasks and for each task t in T a positive (integer) running
time len(t). A positive integer D, called the deadline.
Question: Is there a 2-processor schedule for the tasks that completes within
the deadline, D, i.e. is there a function sigma:T->N such that both of the
following hold:
For all u>=0 the number of tasks t in T for which sigma(t)<=u< sigma(t)+len(t)
is at most 2.
For all tasks t, sigma(t)+len(t)<=D?
Comments: This is the simplest avatar of a very large number of NP-complete
processor scheduling problems and, unsurprisingly given its practical
applications in multiprogramming Operating Systems on small parallel systems,
there is an enormous range of literature on approximation and heuristic
techniques to tackle it, see e.g. relevant sections of this bibliography. The
formal framework given by (a) and (b) can be interpreted as meaning: a) at any
given time at most two tasks are being executed; b) every task has been
completed by the deadline D.
-------------------------------------------------------------------------------
Number: 9
Name: Comparative Divisibility [AN4] 3
Input: A (strictly increasing) sequence A=< a1,a2,...,an> and a (strictly
increasing) sequence B=< b1,b2,...,bm> of positive integers.
Question: Is there an integer, c, such that Divides(c,A)> Divides(c,B), where
Divides(x,Y) (Y being a sequence of positive integers) is the number of
elements, y in Y, for which x is an exact divisor of y?
Comments: You may think that this has an obvious fast algorithm, and, indeed the
algorithm in question is obvious: what it is not is efficient. Consider: how
many bits are needed to store the input data (assuming, without loss of
generality, that an>=bm)? How many steps, however, is this `obvious method'
taking in the worst-case? It is important to realise that representing integer
values in unary is not considered to be a `reasonable' approach (the number
250-1 requires 250 digits in unary but only 50 digits in binary).
-------------------------------------------------------------------------------
Number: 10
Name: Cyclic Ordering [MS2] 3
Input: A finite set, A, and a collection, C, of ordered triples (a,b,c) of
distinct elements from A.
Question: Is there a one-to-one mapping f:A->{1,2,3,...,|A|} (i.e. a function
which maps each element of A to a number between 1 and |A| with no two distinct
elements of A being mapped to the same number) such that for each (a,b,c) in C
one of
f(a) < f(b) < f(c) ; f(b) < f(c) < f(a) ; f(c) < f(a) < f(b)
holds?
Comments: For any triple (a,b,c) there are 6 (six) possible orderings that could
result for ((a),f(b),f(c)). The question being asked is whether there is a
choice of function that forces every specified triple into one of three `legal'
orderings. Garey and Johnson has a typographical error in describing this
problem, whereby each triple `in A' is referred to. Obviously `in C' is
intended.
AS> ЗЫ: Кстати, "Сапер" - это самостоятельный сабж? :)
Это самостоятельный первоапрельский прикол.
E-mail: gate@fidonet.org.il
Voice Phones: 972-4-8330554 (home), 972-5-4481073 (cell)
Bye !
Stanislav (AKA Night's Man) [Team Technion]
---
* Origin: Gate From Another World ... From Haifa, Israel (2:400/520)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
| Тема: |
Автор: |
Дата: |
|
Типы NP-полных задач |
Alexander Shmidt |
10 Jul 2002 20:49:35 |
 Типы NP-полных задач |
Stanislav Shwartsman |
12 Jul 2002 11:00:29 |
|
|
