Типы NP-полных задач

From

Stanislav Shwartsman (2:400/520)

To

Alexander Shmidt

Date

2002-07-24T22:05:33Z

Area

RU.ALGORITHMS

Hello Alexander!

23 Jul 02 08:06, you wrote to All:

 AS> Кто знает про сабж? Сколько их и какие они.

 AS> По поводу кол-ва, их по-моему семь. С тем, что они, собственно,
 AS> представляют - сложнее. Помню только задачу коммивояжера, задачу об
 AS> оптимальном раскрое...

 Между прочим я тебе про это уже отвечал. Если спрашиваешь, так хоть
 потрудись ответы читать.

=== Cut ===
= RU.ALGORITHMS (2:400/520) ===================================================
 Msg  : 176 of 384                          Snt Loc Scn
 From : Stanislav Shwartsman                2:400/520       12 Jul 02  11:00:28
 To   : Alexander Shmidt
 Subj : Типы NP-полных задач
===============================================================================
Hello Alexander!

10 Jul 02 20:49, you wrote to All:

 AS> Насколько я слышал, есть всего семь общих сабжей. Одни из них: задача
 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.

 [skip]

 AS> ЗЫ: Кстати, "Сапер" - это самостоятельный сабж? :)

 Это самостоятельный первоапрельский прикол.

 [skip]

=== Cut ===

 AS> ЗЫ: Кста, "сапер" относится к отдельным типам или он сводится к
 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)