Ці можа праблема быць адначасова паліномны час і невырашальная?

Тэарэма Робертсона-Сэймура на графах непаўналетніх прыводзіць да некаторых цікавым галаваломку.

Тэарэма сцвярджае, што любы мінор-замкнёнае клас графаў можа быць апісана канчатковым лікам выключаных непаўналетніх. Як тэставанне на наяўнасць якога-небудзь дадзенага непаўналетняга можа быць зроблена ў кубічных час (хоць і з астранамічнымі пастаяннымі) адсюль вынікае, што існуе паліномны алгарытм часу для сяброўства тэсціравання ў любой мінорнай замкнёнае клас графаў. Таму ўяўляецца разумным, што праблема павінна разглядацца як у P.

Аднак тэорыя RS не дае нам нават найменшага паняцця аб тым, як вызначыць гарантаваную-канчатковае мноства выключаных непаўналетніх, і пакуль мы не маем іх у боку, мы не можам мець любы алгарытм любога роду , Што яшчэ горш, няма ніякага вядомага алгарытму на самой справе знайсці выключаныя непаўнагадовы, і нават калі ў вас ёсць вялікі спіс з іх, няма ніякага спосабу, якім я ведаю, каб пераканацца, што спіс фактычна завершаны. На самай справе, гэта магло быць на самой справе, магчыма, невырашальнай , каб знайсці спіс выключаных непаўналетніх?

Такім чынам, мае сэнс, каб паглядзець праблему як адначасова паліномны час і невырашальная? Гэта здаецца трохі дзіўным для мяне (які не з'яўляецца спецыялістам у прыватнасці складанасці), але можа быць, гэта цалкам руціна?

37
Проста падказка пытацца ваша пытанне: вы сапраўды <�б> тры пытанні ў вашым пасце, і гэта дапамагло б якасць адказаў, калі вы былі больш наўмысным пра гэта, у прыватнасці, іх нумарацыя. Паколькі некаторыя плакаты адказаўшы 1 толькі некаторыя 2 толькі, і ніхто яшчэ не звярнуўся 3, і гэта робіць яго беспарадак чытаць, калі яны не абвяшчаюць у пачатку якой яны робяць.
дададзена аўтар 0tyranny 0poverty, крыніца

8 адказы

Разгледзім наступны спрошчаны прыклад таго ж з'явы, што многія студэнты знайсці тлумачэнні.

Хай $ F (N) = 1 $, калі ёсць $ N паслядоўныя $ 7 $ S ў дзесятковым пашырэнні $ \ Pi $, а ў адваротным выпадку $ F (п) = 0 $. Ці з'яўляецца гэтая функцыя вычислимая?

Наіўная спроба вылічыць $ F (N) $ будзе проста перайсці да пошуку $ \ Pi $ для $ N $ запар $ 7 $ с. Калі знойдзены, то алгарытм выдае $ 1 $, але ў астатнім .... і тое наіўны алгарытм, здаецца, не ведае, калі для вываду $ 0 $, і таму студэнты часам чакаць, што $ F $ не вылічаць.

Але на самой справе, $ F $ вычислимая функцыя. Калі гэта адбудзецца, што існуе калі заўгодна доўгія паслядоўнасці $ 7 $ з у дзесятковым раскладанні $ \ Pi $, адкрытае пытанне, то $ F $ з'яўляецца пастаянная $ 1 $ функцыі, якая, вядома, вылічыць. У адваротным выпадку, існуе некаторая доўгая паслядоўнасць $ 7 $ S у $ \ Pi $, які мае даўжыню $ N, і так $ F $ з'яўляецца функцыя, якая складае $ 1 $ да $ N $, а затым $ 0 $ вышэй $ N $. І гэтая функцыя таксама можа быць вылічана для любога канкрэтнага $ N $.

Такім чынам, сітуацыя такая, што мы даказалі, што $ F $ вылічаць, выстаўляючы некалькі алгарытмаў, а таксама доказы таго, што $ F $, безумоўна, разлічаны па адным з іх, але мы не ведаем, які з іх. (На самай справе, $ F $ з'яўляецца лінейным вычислимая.) Такім чынам, мы даказалі, што $ F $ вычислимая функцыя, але чыстага доказы існавання, што толькі паказвае, існуе алгарытм вылічэнні $ F $, без яўнага выстаўлення яго.

Здавалася б, тое ж самае з'ява ў вашым выпадку, калі ў вас ёсць вычислимая функцыя, але вы не ведаеце, які алгарытм вылічае яго.


Addition. Let me try to address Thierry Zell's concern about the third question. To my way of thinking, the phenomenon of the question is an instance of the problem of uniformity of algorithms, a pervasively considered issue in computability theory.

Для ілюстрацыі разгледзім пытанне аб тым, ці з'яўляецца дадзены Праграма $ р $ завешваюць на ўваход $ 0 $ да іншай праграмы $ Q $. Хай $ F_p (дз) = 1 $, калі яна робіць, і ў адваротным выпадку $ F_p (дз) = 0 $. кожны такая функцыя $ F_p $ вылічым, па тых жа прычынах у мой $ \ Pi $ функцыі $ F $ вышэй, так як $ р $ не спыняецца ва ўсіх на ўваход $ 0 $, у гэтым выпадку $ F_p $ тоесна $ 0 $ або $ р $ гэта спыніць у $ N $ крокаў, і ў гэтым выпадку нам трэба працаваць толькі $ Q $ для $ N $ крокаў, каб убачыць, калі ён спыняецца, і аддаць выхад за $ F_p (Q) $ да таго часу. Такім чынам, кожны $ F_p $ з'яўляецца вычислимая функцыя. Але сумесная функцыя $ Е (р, д) = F_p (дз) $, двайковая функцыя, з'яўляецца не вычислимы (калі гэта было так, то мы маглі б вырашыць Праблему Прыпынкі: вырашыць калі $ р $ завешваюць на ўваход $ 0 $, дызайн праграмы $ Q $, што б адзін крок EXTRA пасля прыпынку, і спытаць, калі $ P $ прывалаў перад тым $ Q $).

Іншымі словамі, функцыя $ F (р, д) $ вычислима для любога фіксаваны $ р $, але не раўнамерна на $ р $. І такое аднастайнасць пытанні шырока распаўсюджаныя ў тэорыі вычислимости.

У прыкладзе пытання, кожны клас графаў адрозная, але не раўнамерна, так, так як у адказ Тоні не існуе адзінага алгарытму, улічваючы апісанне з клас, каб знайсці калекцыю выключаных непаўналетніх. акрамя любой такой фіксаваны клас, пытанне членства дазволім.

Пытанне, ці з'яўляецца дадзены алгарытм з'яўляецца аднародным ў Дадзены параметр з'яўляецца вельмі распаўсюджанай праблемай у вычислимости тэорыя і адбываецца па ўсім прадмеце.

61
дададзена
Фрэнк, я меў тлумачэнне, што калі ў вас ёсць пятнаццаць запар $ 7 $ S, то першыя адзінаццаць з іх залічваюцца як адзінаццаць паслядоўных $ 7 $ с. Такім чынам, функцыя сапраўды будзе як я апішу яго. У адваротным выпадку, я мяркую, варта казаць аб * максімальных * паслядоўных паслядоўнасцях $ 7 $ з, і я лічу, што гэта з'яўляецца адкрытым пытаннем, ці з'яўляецца адпаведная функцыя вылічыць. (Хаця, калі $ \ Pi $ нармальна, то гэтая функцыя таксама будзе тоесна $ 1 $.)
дададзена аўтар Dane O'Connor, крыніца
@Joel, спасылка ў гэты выдатны адказ быў дададзены да <�я> ТКС StackExchange пытанне «невырашальных атрыбуты P ствараюць перашкода для прыняцця рашэння P супраць NP?» ... Я хацеў бы падзякаваць дзесяць Бринк для прыцягнення ўвагі да такога адказу.
дададзена аўтар Allen Hardy, крыніца
Гэта як $ {\ SQRT 2} ^ {\ квадратны корань 2} $. Напрыклад,
дададзена аўтар Herms, крыніца
Гэта нагадвае мне вельмі падобнай праблемай на мностве праблем я калісьці зрабіў адносна вызначэння дазволь мовы. Праблема складалася ў наступным: Няхай L = {0}, калі ёсць жыццё ў Сусвеце за межамі нашай Сонечнай сістэмы, і L = {1}, калі толькі жыццё ў Сусвеце знаходзіцца ўнутры нашай Сонечнай сістэмы. Тады ўзнікае пытанне: ці з'яўляецца L адрозная?
дададзена аўтар jp2code, крыніца
@Frank: зусім не азначае, што тое ж самае?
дададзена аўтар Assaf Lavie, крыніца

Як ужо згадвалася, адказ на ваша пытанне назву, строга кажучы, <�моцны> няма . Што да іншых вашых пытанняў, было даказана, што яна невырашальная ў <�эм ня> вылічыць выключаныя непаўналетніх для мінорнай замкнёнага класа $ \ mathcal {C} $, калі $ \ mathcal {C} $ з'яўляецца прадстаўлена вам у дурной чынам. Вядома, няма ніякага парадоксу, таму што гэта не азначае, што звязаная з гэтым праблема вызначэння, калі ўваходны граф $ G $ ў $ \ mathcal {C} $ невырашальная. Сапраўды, як вы кажаце па тэорыі Робертсона-Сэймура, гэтая другая праблема не толькі адрозныя, але ў P.

Я мяркую, што я павінен колькасна ацаніць тое, што я маю на ўвазе, не дурныя ўяўленнямі нязначных-замкнёныя сям'і. Fellows і Langston даказаў, што калі ваш непаўнагадовы-замкнёнае клас $ \ mathcal {C} $ задаюцца машыны Цьюрынга $ M $, то невырашальны для вылічэнні без другараднай характарыстыкі $ \ mathcal {C} $. Courcelle, Дауна і Fellows даказаны, што калі $ \ mathcal {C} $ замест гэтага даецца монадическим другога парадкам логікі формула $ \ Phi $, то яна таксама невырашальная для вылічэнні без другараднай характарыстыкі $ \ mathcal {C} $.

Ёсць станоўчыя вынікі для некаторых другарадных-замкнёных сем'яў. Напрыклад, гэта папера Адлера, Grohe і Крэйцер паказвае, што для любога фіксаванага $ K $, яны могуць вылічыць выключаныя непаўналетніх для класа графаў дрэва шырынёй не больш за $ K $. Для вынікаў невырашальнасці, што я ўжо згадваў вышэй, спасылкі:

І.П. Fellows і M.A. Langston. На пошуку, рашэнні і эфектыўнасць алгарытмаў паліномны часу (пашыраны реферат). У Працы 21-га сімпозіума ACM па тэорыі вылічэнняў , старонкі 501-512, 1989.

Б. Courcelle, Р.Г. Даўні і І.П. Fellows. Заўвага аб вычислимости графа нязначнай абструкцыі наборы для монадических ідэалаў другога парадку. Часопіс Універсальнага Інфарматыкі , 3: 1194-1198, 1997..

26
дададзена
+ 1
дададзена аўтар Dane O'Connor, крыніца

Вядома, кожная праблема ў Р адрозная па вызначэнні Р. Гэта было згадана ў папярэдніх адказах.

Але ёсць яшчэ адна праблема тут не ўдалося вырашыць:
Вы, відаць шукаеце алгарытм, які прымае ў якасці ўваходных дадзеных клас замкнуць адносна непаўналетніх і канчатковага графа і вырашае, ці з'яўляецца канчатковы граф у класе.
Ці вы шукаеце алгарытм, які прымае клас, замкнёны адносна непаўналетніх і прадукуе паліномны алгарытм часу, які вырашае сяброўства ў клас.

Вось праблема: Як вы ўяўляеце клас графаў зачынены пад непаўналетнім? Апрыёры не ясна, што кожны клас графаў, замкнёныя адносна непаўналетніх (звычайна клас, які змяшчае графікі бясконцага мноства класаў ізамарфізму) мае разумнае прадстаўленне ў выглядзе канчатковы аб'екта (які можа быць апрацаваны алгарытмічная) на ўсіх. Пад канчатковым прадстаўленнем я маю на ўвазе формулу, якая вызначае клас у той ці іншай ці нешта падобнае.

Цяпер граф другарадны тэарэма дае нам добрае ўяўленне кожнага такога класа: спіс Just канчатковае мноства забароненых непаўналетніх. Калі гэта ваша ўяўленне класа, то вы атрымаць паліномны алгарытм часу, які вырашае сяброўства ў класе.

Калі вы асядае на іншае ўяўленне (і вы павінны прыдумаць нейкі адзіным чынам апісаць свой клас канчатковых аб'ектаў, каб быць у стане сказаць што-небудзь алгарытмічная наогул, я думаю), гэта не можа быць магчыма прыдумаць алгарытм што вылічае канчатковае лік забароненых непаўналетніх ад прадстаўлення класа.

15
дададзена

Дональд Пуга зрабіў такі прагноз у апытанні ( http://www.cs.umd.edu/~ gasarch/дакументы/poll.pdf ) аб тым, калі P супраць NP будзе вырашана:

<�Р> Гэта будзе вырашана альбо 2048 ці   4096. У цяперашні час я некалькі песімістычна. вынік будзе   сапраўды найгоршы сцэнар: а менавіта, што   хтосьці даказаць «P = NP, таму што   толькі канечны лік перашкод да   супрацьлеглая гіпотэза »; такім чынам,   будзе існуе паліномны рашэнне часу   да SAT, але мы ніколі не даведаемся яго   складанасць!
8
дададзена

Мне здаецца, ёсць два ўзроўні, якія працуюць тут.

Для любога мінорнай замкнёнага класа графаў, ёсць з'яўляецца некаторага канчатковага мноства выключаных непаўналетніх, і, такім чынам, існуе паліномны алгарытм часу для сяброўства тэставання ў , што класа (мы не «т павінны ведаць, што ў відавочнай форме алгарытм, мы проста ведаем, што існуе.)

Аднак, на ўзроўні вышэй, выпісваючы гэты алгарытм відавочна ўключае ў сябе пошук канчатковае мноства выключаных непаўналетніх у відавочным выглядзе, і гэта можа быць цяжка/невырашальнай.

5
дададзена
Больш той момант, «узровень вышэй» нават не цалкам пэўны алгарытмічная - як вы вызначаючы «мінорны замкнёнае клас» у якасці ўваходных дадзеных? Дастаткова агульны спосаб будзе паказаць яго ў якасці прэдыкатаў першага парадку, можа быць, і тады з'яўляецца , верагодна, сутыкнуцца з праблемамі невырашальнасці. Вядома, калі вы карыстаецеся вынікі R-S і паказаць другарадную-замкнёнае клас канчатковым мноствам выключаных непаўналетніх, то «ўзровень вышэй» становіцца даволі трывіяльна.
дададзена аўтар panzi, крыніца
Я не магу знайсці паперу, але я памятаю, як чытаў доказ таго, што «вышэй узровень» праблема (улічваючы, я лічу, першым парадак прэдыкатаў для мінорнай-замкнёнага класа) не адрозная.
дададзена аўтар mjqxxxx, крыніца

Праблема заключаецца ў Р, калі яна <�моцны> адрозная за паліномны час . Так што, калі гэта невырашальнай, то ні ў Р, ні ў НП. Гэта нават не рэкурсіўнае. См http://en.wikipedia.org/wiki/Complexity_class .

3
дададзена
Сапраўды ! Не варта блытаць паміж «рэкурсіўнай» і «перечислимым». Дзякуючы.
дададзена аўтар BradS, крыніца
Ці ёсць нейкая блытаніна паміж праблемамі прыняцця рашэнняў і разлік іх вырашэння? А (рашэнне) задача аб існаванні рашэння даўжынёй да можа быць у P, але вылічыць гэтае рашэнне можа быць экспанентным, няма ў цяперашні час немагчыма. Гэта менавіта з-за неканструктыўную працэдуру доказы.
дададзена аўтар BradS, крыніца
Вы проста жадаеце «рэкурсіўны» там замест «перечислимого». Шмат рэчаў толькі звыклымі яшчэ R.E. Тэарэмы ПА напрыклад (і больш да кропкі, любы ня рэкурсіўнае мноства R.E.).
дададзена аўтар Eric Hogue, крыніца
Гэта, строга кажучы, дакладна, але на самой справе не атрымлівае на парадоксе, які турбуе Гордан-Royle. Адна разумная інтэрпрэтацыя Робертсан-Сэймура з'яўляецца тое, што ў нейкай абстрактнай неканструктыўнай сэнсе гэта даказвае існаванне паліномны алгарытму для задачы. Для выкарыстання алгарытму неабходна канчатковае колькасць дадзеных, але вядома, што не існуе алгарытму для знаходжання гэтых дадзеных (Tony Хюинь дае спасылкі ў сваім адказе). Гэта даволі дзіўная сітуацыя.
дададзена аўтар arsmath, крыніца

Я думаю, што тое ж самае з'ява лягчэй зразумець у Domino Праблема . Гэта не вырашальная Ці дадзены набор можа забрукаваць плоскасць ці не. Гэта азначае, што калі ваш ўклад не з'яўляецца наборам, то не можа выводзіць адказ алгарытму. Аднак, для любога фіксаванага набору, адказ Так або Не, так трывіяльны алгарытм (які не мае ніякага ўкладу) адказвае на яго. Толькі ў выпадку непаўналетніх, нават для фіксаванага набору, то ёсць іншы ўваход (графік), і мы павінны Robertson-Сэймура.

0
дададзена

Калі G з'яўляецца нязначным з Н, то нейкім чынам можна даказаць у P-час (дэманструючы зніжэнне). Гэта азначае, што калі ёсць невядомы алгарытм паліномны час ($ O (| H | ^ 3) $ у гэтым выпадку) для прыняцця рашэння, калі фіксаваны G з'яўляецца непаўналетнім дадзенай Н, то, калі я не памыляюся, ёсць таксама вядомы пэўны алгарытм для вырашэння гэтай, а менавіта універсальны пошук Левіна.

0
дададзена