требуется доказать что задача является NP-полной, ну собственно доказательство заключается в том что нужно найти в книжке 
(М.Гери, Д.Джонсон - Вычислительные машины и трудно решаемые задачи) эту задачу или бо показать что она включает в себя 
NP-полную. Вот только не могу сообразить что это за задача



Это сообщение отредактировал(а) Shadowlord - 14.12.2009, 20:33

что бы доказать что проблема N -complete , мы должны трансформировать её  input  в INPUT проблемы которую мы уже знаем как решить in polynomial time  ( каждый input   элемент  одной проблеммы трансформируется в input элемент другой проблемы так что если этот элемент до трансформации давал ответ "true" для  оригинал алгоритма, после трансформации он будет давать "true" для второго алгоритма.

После этого мы запускаем второй алгоритм 
Он решает проблему in polynomial time на этом трансформированном input.
Затем  мы обязательно должны быть способны verify его ответ in polynomial time .

В буквальном смысле : после того как  клеями материалы склеены вы просто вручную  in polynomial time   проверяете что они склеены попарно 
Вы можете этого и не делать но вы должны быть физически способны это сделать .

Qawra: Ну вообще-то NP-полнота это когда наоборот, нет полиномиального алгоритма ;)

Да , его нет , и в то же время 
несуществует математического доказательства что такой алгоритм для этой проблемы невозможно создать . 

Ну задача в этой теме вообще в том чтобы доказать, что задача NP-полна, а вы про поиск полиномиального пишете 

Правда, по справедливости, я сам более умного пока предложить не могу  Есть идеи построить какой-нибудь граф, чтобы исходная задача превращалась в графовую, про которую будет известно, что она NP-полна. Но вот отсюда же не будет следовать NP-полнота исходной задачи...

И всё же, граф можно такой построить: добавить в него по вершине для каждого материала, по вершине для каждого клея, и соединить рёбрами каждый клей с теми материалами, которые он клеит. Тогда надо найти такой путь в этом графе, который бы содержал все вершины-материалы, и содержал как можно меньше различных вершин-клеев... Не знаю, есть ли такая задача в Гэри-Джонсоне, сейчас нет времени посмотреть. Но если честно, есть сомнения, что именно такая задача есть там 

Так я и предлагаю доказать что задача NP - complete .
По определению  доказать . 
Что-бы быть NP - complete  задача должна :

1 - не иметь polinomial time алгоритма  
2 - не иметь математического доказательства что такой  алгоритм невозможно построить

Но это ещё не доказательство .
Там есть  доказанная " first NP - complete " проблема о logic gates 

Остальные  NP - complete проблемы  разрешено не доказывать математически а использовать то схему которую я описывала ранее.
Эта схема  опирается на теорию NP - complete languages. 
И доказано что если input интересующего алгоритма удаётся перевести "однозначно " в input polynomial time алгоритма то оригинальный алгоритм NP - complete . 

Вы заблуждаетесь.
И говорите неправильные вещи

Извините  
Так учат ....., так сказать "NP-complete для начинающих". 
C научной точки зрения  он наверно будет выглядеть по другому и обьясняться иначе ... 
Но на начальном этапе обучения  , NP -complete именно такой .
Ничего с этим не поделаешь ,побочный эффест модульности современного образования .

Уточню

Вы говорите ерунду.
Ну бред с точки зрения теории вычисления.


Никто еще не доказал, что у класса НП нет полиномиального алгоритма. Никто не доказал что его не может быть.

Пункт 2 не имеет никакого отношения, к реальности.


Задача принадлежит является НП полной, если она принадлежит к класу НП, и к ней сводиться любая задача из класса НП.

Всё правильно 
И вы тоже правы (с точки зрения теории вычисления).
Меня c вашего разрешения можно перефразировать так: 
" Polynomial time алгоритм не должен быть известен ,
  как и не должно быть известно математические доказательство его отсутствия "

                      Тут всё просто :
если известен Polynomial time алгоритм 
                                        - проблема уходит в класс Polynomial time ;
если доказано что его нет -уходит это проблема в Exponential или
в Non-Computable  классы.

А в NP-complete остаётся то что "не имеет " и для чего " не доказано ".

Вы опять заблуждаетесь.

1) Неверно. Нет такого требования. Его нет. Вас дисинформировали.

2) Неверно. Нет такого требования.  

3) Если известен полиномиал тайм алгоритм, то вполне возможно что проблема уйдет и в класс НП.

4) Нет, вы не правы, между P  и PSPACE  есть гигантская пропасть. И где в этой пропасти упадет НП пока еще не известно.


5) Нет.



Советую вам, если вам интересно почитать соответствующую литературу. Хотя бы учебник Ульмана или Спенсера, или Ахо.

Ну хотя бы никому не говорите, то что вы знаете о НП, а то еще кого нибудь дурному научите. 


;)

Это всё опять  с вершин научной теории .
Меня  не дезинформировали а официально обучили в рамках
Data Structures and Algorithms 1 модуля . 
Поэтому я могу говорить что я знаю что такое NP-complete на этом уровне.
То что вы говорите может быть правдой а может и не быть ей .
Я этого не знаю Data Structures and Algorithms 2 модуль будет через год , тогда наверно и узнаю . 
Пока , я не вижу смысла с вами спорить . Сами подумайте -
Человек задавший вопрос был  студентом . 
Он явно не владел научной теорией на вашем уровне  . 
Если бы вы вместо того что-бы  критиковали меня  написали бы свой вариант ответа  вы бы сами это поняли .
Вы ответа на вопрос студента не написали   

Вы знаете. 

Многолетний опыт преподавания, в вузе показывает.

Есть гигантская пропасть, между тем что сказал преподаватель и тем что из этого понял студент.
Достаточно перепутать лишь один квантор и понять наоборот.

Всего лишь скажу вам еще раз, ваше понимание не верное. Хотите верить в него? - Это ваше право. Но все же ,не стоит дизинформировать других людей.
Это уже некрасиво.  

А идей  какой NP-полной можно свести не у кого толком нет, а то все мои варианты были не приняты