Ці з'яўляецца P = NP стаўленне да знаходжання доказы паўсядзённых матэматычных сцвярджэнняў?

Адмова ад адказнасці: Я не ведаю шмат пра тэорыі складанасці за яе межамі, скажам, добры старшакурсніка класа.

З павелічэннем частаты я, здаецца, сустракаючы прэтэнзіі тэарэтыкаў складанасці, што, у малаверагодна выпадку, што P = NP даказаныя і алгарытме з разумнымі канстантамі знайшлі, матэматыкі не спрабуйце даказаць рэчы больш Beause мы маглі б проста выкарыстоўваць наш P- алгарытм часу для пошуку доказаў. Звычайна гэта частка аргументу, чаму ўсё матэматыкі і логікі павінны клапаціцца шмат пра P =? = NP.

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

Тым не менш, гэта цалкам зразумела з апісання Clay інстытута, што P = NP мае дачыненне толькі да класаў задач, спараметрированного некаторым лікам $ N $, для якіх мы ўжо даказалі ўсе тры з наступных дзеянняў:

  1. пытанне не залежыць ад выбраных намі аксіём ($ T \ vdash \ Phi \ ві Т \ vdash \ атр \ Phi $)
  2. любы доказ прапановы павінны мець памер у большасці полинома ў $ N $
  3. якія-небудзь доказы адмаўлення прапаноў павінны мець памер у большасці полинома ў $ N $

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

Гэта бянтэжыць мяне. Большасць прапаноў матэматыкаў клапаціцца пра не прыходзіць у цэлалікавых параметризованных класаў, не кажучы ўжо пра класах з вядомымі межамі доказы памеру. Звычайна яны прыходзяць у класах памеру 1 без ведання карэктара памеру. Ці ёсць нейкі трук для павароту відаў вынікаў матэматык неабыякавыя ў гэтыя цэлалікавых параметризованном-полінаміяльна-абмежаваных класы?

Прыклад: як вы гэта робіце на пытанне аб тым ці няма СН не залежыць ад ZFC?

Кук і JSL артыкул Reckhow ў Адносная эфектыўнасць прэпазіцыянальнага Proof сістэм (які, здаецца, адпраўная кропка для літаратуры) на самой справе гаворыцца, што калі ўзяць клас праблемы складаецца з усіх сцвярджэнняў ў некаторай сістэме доказаў ( такія як першы парадак падлік прэдыкатаў), вазьміце даўжыню прапановы ў якасці параметру, і ўзяць на сябе пытанне, што «гэта пацягнула за сабой аксіёмы», то ў той час артыкул быў надрукаваны (1979) няма рэальных доказаў сістэма была вядомая, каб мець жаданае ўласцівасць, і некаторыя з іх былі вядомыя <�моцны> не , каб мець жаданае ўласцівасць.

Я мяркую, што я з'яўляюся трохі лянівым тут, так як даследаванне, якія праблемы маюць гэта ўласцівасць у цэлым падполу з вялікай колькасцю літаратуры, я мог чытаць, але на самой справе я зацікаўлены толькі ў Ці ці не тое, што падмосце ў станоўчых-выніках ў актуальным стане абгрунтаваць прэтэнзіі я чуў у апошні час. Спасылка на дакумент, які змяшчае «трук» вышэй будзе штраф у якасці адказу.

30
Ламин: «Калі праблема ў Р, нават калі ён мае вялікі паказчык і канстанта, гэта будзе лёгка адзін дзень, каб вылічыць.» На жаль, я не згодны: няма ніякай надзеі, калі канстанта ці паказчык мае памеру $ 3 !!!!!!!!!!!!!!!!!!!!!!!! $ (итерированные факториалы), да прыкладу!
дададзена аўтар Alex Angas, крыніца
Зазор прадастаўляецца людзьмі паміж паліномны і экспанентным часам можа быць апраўданы ў адпаведнасці з законам Мура. Гэта прадугледжвае, што вылічальныя магутнасці растуць экспанентна (гэта можа мець мяжа з-за некаторыя крамянёвыя прыстойнасці, але выкарыстоўвае іншыя тэхналогіі, каб працягнуць гэты рост можна чакаць). Калі праблема ў Р, нават калі ён мае вялікі паказчык і канстанта, гэта будзе лёгка адзін дзень, каб вылічыць.
дададзена аўтар BradS, крыніца
Я меў на ўвазе, што вылічальныя магутнасці растуць хутчэй, чым складанасць любой праблемы ў P (калі закон Мура дакладна). Гэта дазваляе некаторую надзею вырашыць гэтую праблему за адзін дзень.
дададзена аўтар BradS, крыніца
Я думаю, што ваш «<�я> любы </я> доказ [адмаўлення] прапановы павінны мець памер у большасці полинома ў $ N $» павінна быць «<�я> некаторыя </я> доказ ...»; нам проста трэба знайсці адзін доказ сцвярджэння або яго адмаўленне.
дададзена аўтар warspyking, крыніца
@ Робін-Адамс: так, сапраўды, дзякуй (адрэдагаваны выправіць).
дададзена аўтар Billy ONeal, крыніца
Я бачыў Марцін Дэвіс гаварыць у мінулым годзе, і ён сказаў нешта ўздоўж ліній ён не быў бы зьдзіўлены, калі P = NP, але толькі таму, што людзі схільныя забываць, як адваротны алгарытм паліномны час можа быць. Нават калі б мы мелі P-часовай алгарытм для праверкі доказаў, не можа быць любога практычнага выкарыстання.
дададзена аўтар user4087, крыніца
Вельмі педантычны момант: Я думаю, што вы маеце на ўвазе $ T \ vdash \ Phi $ або $ T \ vdash \ атр \ Phi $ »пад 1, а не $ T \ vdash \ Phi \ ві \ атр \ Phi $ », што справядліва для ўсіх $ \ Phi $ (калі мы выкарыстоўваем класічную логіку).
дададзена аўтар mosmic12, крыніца

8 адказы

Дазвольце мне вырашыць праблему ў пачатку зыходнага пытання: Калі P = NP былі даказаныя і алгарытм з разумнымі канстантамі знайшлі, што матэматыкі перастаюць спрабаваць даказаць гэта? Адпаведны NP набор у гэтай сітуацыі, як уяўляецца, $ L_1 $ адказу Райана Ўільямса, які я лічу (або дэкадаванне) як мноства пар, якія складаюцца з прапановы $ P $ будуць даказаныя і верхнім мяжой $ N $, напісанымі у аднамеснай натацыі, для доказу даўжыні. Калі б мы мелі паліномны алгарытм часу для гэтага мноства NP, то я мог бы ўжыць яго наступным чынам. Вазьміце $ P $, каб быць некаторы здагадка, што я адчуваю жаданне працаваць, і ўзяць $ N $, каб быць больш, чым любы доказ таго, што я паспеў напісаць у маім жыцці. Калі алгарытм, ужыты да гэтых уваходам, кажа «не», то я не павінен працаваць над гэтай праблемай, таму што любы доказ было б занадта доўга для мяне, каб напісаць. Калі алгарытм кажа «так», то я да гэтага часу не павінны працаваць над праблемай, так як паліномны час алгарытм Райана $ L_2 $ можа знайсці доказ для мяне. Усё гэта, аднак, залежыць ад вельмі аптымістычнага разумення «разумных канстант». $ П $ Я абраў (я спадзяюся) даволі вялікі, так што нават квадратычны час алгарытм (з малым каэфіцыентам на квадратычнай члене) можа заняць працяглы час (даўжэй, чым маё жыццё).

Сутнасць заключаецца ў тым, што, калі P = NP былі даказаны з праўдападобнымі канстантамі часу працы, гэта не было б па-дурному для мяне, каб працягваць спрабаваць даказваць тэарэмы. (Нават калі б гэта было па-дурному, я працягваю спрабаваць так ці інакш, збольшага таму, што гэта весела, а збольшага таму, што людзі маглі б маё доказ лепш лексікаграфічныя першым.)

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

31
дададзена
Нягледзячы на ​​тое, што я не магу ўспомніць ні адной з дэталяў экспромтам, я бачыў некалькі алгарытмаў, выхад экспанентна доўгі спіс за паліномны час/дэталь на ім.
дададзена аўтар Damian, крыніца
@Andreas Blass: Вы згадалі «сістэму, у якой доказ павінна зрабіць, для гэтых мэтаў, а не быць проста аксіёма сістэмы, як ZFC з традыцыйнымі аксіёма і асноўны логікай Гэта павінна быць сістэмай, якая дазваляе фармальна ўвесці вызначэння .. на самай справе, ён павінен цесна аппроксимировать, што матэматыкі на самай справе пісаць «. Ёсць два такіх практычна прыдатных сістэм (у тым ліку аўтаматычных шашак доказы): Ізабэла </а & GT "отн =" NOFOLLOW noreferrer "> cl.cam.ac.uk/research/hvg/Isabelle /"> Ізабэль </а & GT </а> і Мицар </а & GT" отн = "NOFOLLOW noreferrer"> mizar.org "> Мицар </а & GT </а>;.
дададзена аўтар Ferruccio, крыніца
дададзена аўтар Ferruccio, крыніца
@ Цім: Вы кажаце аб выхадзе або выхадзе даўжыня ?
дададзена аўтар Christi, крыніца
@Adam: любы алгарытм, які выводзіць доказ (калі яна існуе) дадзенае прапанова мае час працы абмежаваны знізу па даўжыні найкарацейшай карэктура трэба часу, каб запісаць адказ! І алгарытм, які працуе хутчэй, але не выводзіць доказ не было б вельмі прыемна матэматыкі; калі кампутар сказаў мне «блізнюк запальвае гіпотэза дакладная», не даючы доказы таго, што не ўплывае на маё жыццё наогул.
дададзена аўтар phunehehe, крыніца
@Adam: Гэта на самай справе не так ужо і рэдкасць, каб алгарытмы, якія працуюць у паліномны час на выхадзе, а не на ўваходзе. Напрыклад, вылічальнае пастаянны з'яўляецца #P цяжка, але яна можа быць вылічаная ў паліномны час яго кошту.
дададзена аўтар Joel Brown, крыніца
@gowers: Выхад. Даўжыня пастаяннага полінаміяльна памеру ўваходу, таму мы не можам чакаць, алгарытм, які працуе ў паліномны час ад даўжыні выхаду.
дададзена аўтар Joel Brown, крыніца
Дзякуй, Андрэас. Дазвольце мне перафразаваць зразумець, што вы падалі :. Ніхто не спрабуе сцвярджаць, што ўсё, што будзе адбывацца ў паліномны час у памер прапановы </я> Адзіныя прэтэнзіі, знаходзяцца рэчы, якія адбываюцца ў паліномны час у клавішы <�я> памер найкарацейшага доказы, калі такія маюцца. Гэты бок крокі пытанне аб фармальнай незалежнасці, калі мы робім выгляд, што «няма доказаў» не азначае «самы кароткі доказ бясконца доўга». Гэта змяненне, з-прэтэнзіі, безумоўна, пакідае нас з чымсьці, якое аб'ектыўна правільным (хоць, я павінен сказаць, суб'ектыўна менш задавальнення).
дададзена аўтар Billy ONeal, крыніца
Я хацеў бы таксама дадаць, што ён адчувае сябе крыху своеасабліва: прапанова з'яўляецца укладам у працэс, і пагадненне, як правіла, для вымярэння асімптатычнага часу ў памеры ўводу, а не памеры выхаду. Але аргумент застаецца правільным; ён проста выкарыстоўвае незвычайную метрыку.
дададзена аўтар Billy ONeal, крыніца
Я не сказаў, што было рэдкасцю для алгарытмаў да <�я> быць </я> Паліна іх вытворчасці; Я сказаў, што гэта было незвычайна выкарыстоўваць яго ў якасці асноўнага паказчыка [дыхтоўнасці алгарытму, у].
дададзена аўтар Billy ONeal, крыніца
Вельмі цікавае назіранне: «людзі маглі б маё доказ лепш, чым лексікаграфічныя першы»
дададзена аўтар Harry, крыніца

Я сам лічу, што доказы таго, што P = NP не з'яўляецца ні неабходным, ні дастатковым для атрымання кампутараў для вырашэння задач матэматыкі.

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

Не трэба: як матэматыкі мы не вырашым цалкам агульную праблему, «Ці ёсць доказ гэтага сцвярджэння, што займае менш п сымбаляў?» Хутчэй за ўсё, мы арыентуемся на вельмі невялікі падклас, які складаецца з цікавых і значных праблем, і мы шукаем цікавыя і значныя доказы. Я сам лічу, што гэтая праблема адрозная за паліномны час (груба кажучы, таму што я не веру, што ў людзей ёсць асаблівыя здольнасці, што кампутары будуць вечна не хапае).

17
дададзена
@AndrewMacFie: Не толькі таму, што цікавыя доказы вучаць нас, як даказаць, іншыя рэчы, але і таму, што цікавыя доказы прапануюць нам іншыя цікавыя <�я> пытанні , што мы маглі б шукаць доказы для. Нават у самым аптымістычных сцэнарах P = NP, пытанне аб фармуляванні цікавых і карысных пытанняў, будзе па-ранейшаму застаюцца матэматыкі.
дададзена аўтар Joshua Grochow, крыніца
Што такое кропка доказы быць цікавым, калі людзям больш не трэба рабіць якой-небудзь прувинг? Нам падабаюцца цікавыя доказы, таму што яны вучаць нас, як даказаць іншыя рэчы.
дададзена аўтар harsh, крыніца

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

$ L_1 = \ {P1 ^ п ~ | ~ п \ у {\ mathbb N} $ і прапановы $ P $ мае доказ у сістэме з не больш чым $ N $ сімвалаў $ \} $.

$ L_2 = \ {P1 ^ да ~ | ~ п \ у {\ mathbb N} $ і прапановы $ P $ мае доказ у сістэме і трохі лексікаграфічныя першае доказ $ P $ $ да $ -ю з'яўляецца 1 $ \} $.

Калі $ P = NP $, то два вышэй моў могуць быць вырашаны за паліномны час (для «паўсядзённых» сістэм доказаў). Гэта дазваляе вырабляць доказ любога фіксаванага прапанову $ P $, калі яна існуе, за час, паліномны ад даўжыні найкарацейшага доказы. <�Моцны> Нам не трэба ведаць даўжыню найкарацейшага доказы загадзя. Напрыклад, калі СБ адрозная за лінейнае час (адкрытая праблема), то ніжэй працэдура павінна быць здзяйсняльная не больш чым квадратычнай або кубічны раз у даўжыні найкарацейшага доказы.

Я апішу, чаму гэта так. Хай для пэўнасці, што час працы для прыняцця рашэння як $ L_1 $ і $ L_2 $ не перавышае $ C \ CDOT п $, дзе $ N $ даўжыня уваходнага сігналу. Па-першае, запусціць праграму за $ L_1 $ на $ P1 $, $ (\ атр P) 1 $, $ P1 ^ 2 $, $ (\ атр P) 1 ^ 2 $, $ P1 ^ 4 $, $ (\ атр P) 1 ^ 4 $, $ П1 ^ 8 $, $ (\ атр P) 1 ^ 8 $, і г.д., пакуль праграма выхадаў "так". Час працы гэтай працэдуры складае каля $ C (D + 2) 2 ^ да $, дзе $ D $ ёсць даўжыня прапановы і $ 2 ^ да $ з'яўляецца найменшай ступенню двух, што перавышае даўжыню самага кароткага доказы. Гэта вызначае верхнюю мяжу на даўжыню найкарацейшага доказы з дакладнасцю да мультыплікатыўны двух разы. (Пры выкананні «двайковы пошук» аналагічным чынам на адрэзку $ [2 ^ {k-1}, 2 ^ к] $ са злёгку змененым мовай, вы маглі б раскрыць мінімальную даўжыню доказы, калі вы хочаце, тэлефануйце па тэлефоне гэта $ P $. для нас дастаткова, каб мець добры верхні мяжа даўжыні.)

Выкажам здагадку, што выхад праграмы "так" на $ P $ (замест $ \ атр P $). Затым запусціце праграму за $ L_2 $ на $ P1 ^ 1 $, $ P1 ^ 2 $, $ \ ldots $, $ P1 ^ р $ (ці да $ P1 ^ {2 ^ k} $). Кожны выклік вяртае біт лексікаграфічныя першае доказ $ P $, які мае даўжыню $ P $. Агульны час працы складае каля квадратычнага па $ р $ (з некаторымі дадатковай канстантай $ C $ і $ D $).

Калі вы сцвярджаючы, што нават такога роду часу выканання павінны яшчэ быць непрактычныя для «паўсядзённых матэматычных меркаванняў», я б не пагадзіцца. Калі канстанта $ з $ у алгарытмы былі даказальна гіганцкім (ці ў больш агульным плане, ступені полиномов часу працы), то гэта было б правільна, але ў нас вельмі мала ведаў аб межах на $ C $ ў гэты час.

15
дададзена
@Adam, вядома, вам трэба выкарыстоўваць ўстойлівую сістэму дастаткова багатай, каб выказаць доказ незалежнасці гіпотэзы кантынууму ад ZFC. Але я не ўпэўнены, што ваша кропка. Можна знайсці шмат іншых прыкладаў тэарэм вы не можаце даказаць у дадзенай сістэме доказаў; якім чынам гэтае шоў P = NP не мае ніякага дачынення да пошуку доказаў паўсядзённых матэматычных сцвярджэнняў?
дададзена аўтар David Hammen, крыніца
+1. Што тычыцца канстант, можа быць, варта адзначыць, што Харві Фрыдман паказаў адзін сказ, які даказальна з дапамогай ZFC + «для ўсіх $ N $ існуе моцна $ N $ -Mahlo кардынал» з не больш чым $ 10 ^ 6 $ сімвалаў, але гэта ня даказальна ў адзіночку ZFC з дапамогай менш чым $ 10 ^ {1000} $ сімвалаў (у абодвух выпадках, якія дазваляюць абрэвіятуры). cs.nyu.edu/pipermail/fom/2006-February/010056. HTML Хоць прапанову Фрыдмана наўпрост не разглядаецца пытанне Адама, як пастаўленае, ён ілюструе тонкасці абмяжоўвае фактычных памераў фактычных доказаў (у адрозненне ад іх асімптатычнага росту).
дададзена аўтар Joel Brown, крыніца
Ваш алгарытм не спыняецца, калі я выбіраю ZFC як мае аксіёмы і кантынуум-гіпотэза, як маю прапанову.
дададзена аўтар Billy ONeal, крыніца
@RyanWilliams ZFC дастаткова багаты, каб выказаць доказ незалежнасці гіпотэзы кантынууму ад ZFC. Але вы павінны закадаваць заяву (незалежнасці) на мове ZFC (як аднаго прапановы). Так што я згодны з Адамам, што гэта віна вашага алгарытму, а не віна ZFC.
дададзена аўтар Anonymous, крыніца

У артыкуле «Асабісты погляд Сярэдне-Case Складанасць» Расэл Импальяццо лічыць пяць розных светы, у залежнасці ад сярэдняга выпадкі складанасці NP-поўных задач, адзін з іх ( «Algorithmica»), якія маюць P = NP.

Розныя светы тлумачацца выкарыстанне вядомага анекдота Гаўса і яго настаўнікаў, задавалых клас, каб дадаць лік ад 1 да 100, так што гэта добрае чытанне для любога матэматыка. У цэнтры ўвагі артыкулы пра наступствы пяці розных магчымасцяў на настаўніку будучы ў стане праблемы, для якіх ён ведае, што рашэнне, але якія Гаўса не можа вырашыць. Так што гэта не адказвае на пытанне пра «трук, каб ператварыць матэматыку ў NP-задач», але дае ўяўленне пра пытанне ў загалоўку.

5
дададзена
5
дададзена
@Adam: «кароткі» доказ, як гэта вызначана Іосіфу відавочна полінаміяльна bouned. Гэта на самай справе пастаянная! Я лічу, што зацвярджэнне «доказ можна знайсці ў паліномны час ад даўжыні заявы і даўжынямі найкарацейшага доказы» робіць вельмі добрую працу падвядзення вынікаў.
дададзена аўтар Nautical, крыніца
Калі вы не звяртаючы ўвагі на памер ўваходу, навошта выкарыстоўваючы алгарытм, адзін і толькі дабрачыннасць з'яўляецца час яго працы ў якасці функцыі <�я> ад памеру уваходнага? Калі мы выкажам здагадку, што доказы больш, чым $ 10 ^ {12} $ не мае значэння, то поўны перабор таксама пастаянная час, так што асімптатычна так жа добра, як і любы іншы алгарытм. Горш таго, калі ваш алгарытм мае канстанта, якая складае $ 2 ^ {2 ^ {2 ^ {10 ^ {12}}}} $ ИИТ на самай справе горш, чым поўны перабор не толькі ў асімптатычна умовах, але абсалютным выразе, як добра! Такая небяспецы выкарыстання асімптатычнага аналізу ў сітуацыі, калі ўсе пастаянна
дададзена аўтар Billy ONeal, крыніца
(Дарэчы, ваш адказ быў бы зрабіў добры каментар)
дададзена аўтар Billy ONeal, крыніца
Дзякуючы Язэпу, але маё пытанне ў іншым - вы пішаце "абмежаваць ўвагу полінаміяльна-доўгія доказы», ​​у той час як я пад сумненне практычнасць гэтай здагадкі. Я на самой справе лічыцца размяшчэнне ў тэорыі stackexchange складанасці, але ў канчатковым рахунку суб'ектыўная частка ( «прапазіцыі матэматыкі клапоцяцца пра») з'яўляецца найбольш тонкая частка, таму я папрасіў матэматыкаў замест тэарэтыкаў складанасці.
дададзена аўтар Billy ONeal, крыніца
Іншымі словамі, я згодны ... ўсталяванне P = NP (г.зн. існаванне алгарытму паліномны па для абмежаванага памеру пошуку доказы [дзе паліномны па азначае Паліна ў памеры доказаў абшукалі над]) не рэч, што б рэвалюцыянізавала (фармальнае доказ пошуку аспект) матэматыкі. Пошук хуткі алгарытм для пошуку доказы гэта тое, што б рэвалюцыянізавала матэматыку. Але, натуральна, паняцце хуткага алгарытму значна менш канкрэтна, чым паняцце алгарытму паліномны па.
дададзена аўтар user2808054, крыніца
Паліномны час крыху не вельмі важна, для падтрымкі гэтага пункту гледжання, так як зліццё паняццяў «паліномны часу» з «хутка, ва ўсіх выпадках я клапачуся аб». Сутнасць у тым, перабор для доказу памеру <= 10 ^ 12 значна, значна больш павольна, чым можна чакаць, агульны алгарытм паліномны часу для абмежаванага памеру доказы пошуку быць. Але, вядома ж, сплаў «паліномны час» з «хутка, ва ўсіх выпадках я клапачуся аб», ну, вынікаючай ...
дададзена аўтар user2808054, крыніца
@Adam: Я бачу вашу ўвагу, і вы маеце рацыю, што, у агульным выпадку, даўжыня доказы не могуць быць абмежаваныя. Што тычыцца практычнасці здагадкі аб кароткіх доказах: Калі кароткі вызначаюцца, скажам, на менш чым $ 10 ^ {12} $ знакаў у некаторай фармалізацыі, то не зразумела, людзі могуць зразумець доўгія доказы.
дададзена аўтар Joseph O'Rourke, крыніца

Іншыя ўжо далі добрыя адказы, але я хацеў бы адзначыць, што абмежаванне «разумных канстант» патэнцыйна значна больш жорсткімі, чым думае большасць людзей. Напрыклад, у рэальным свеце, прастора мае тэндэнцыю быць больш дарагімі, чым час. Таму выкажам здагадку, што існуе некаторы доказ гіпотэзы Рымана, якая ледзь досыць малы, што мы можам толькі толькі рэалізаваць кампутарную праграму, якая пры запуску з выкарыстаннем усіх сусветных рэсурсаў кампутара, можа ледзь-ледзь ступіць праз усе доказы і праверыць яго ўнутры прымальныя чалавек часовых рамкі. Хутчэй за ўсё, мы б не мелі дастаткова рэсурсаў, каб <�я> запісаць </я> такое доказ відавочна; кампутары, верагодна, будуць пастаянна паўторна выкарыстоўваць прастору і сціраць рэчы, якія былі выкарыстаныя пры праверцы папярэдніх этапаў доказы, але што больш не будзе неабходнасці. План, які Андрэас Blass акрэслены, пісаць у відавочным выглядзе даўжыню доказы ў Унарный і працуе наш алгарытм магіі на гэтым ўваходзе, не быў бы магчымы ў гэтым выпадку.

Ва ўсякім выпадку, справа ў тым, што ў сучасным свеце, ня варта думаць пра доказе, неяк, што займае ўсяго некалькі мільёнаў сімвалаў, каб запісаць у відавочным выглядзе. Нягледзячы на ​​тое, што гэта важнае назіранне, што было б рэвалюцыйным выявіць алгарытм для пошуку доказаў таго, што з'яўляецца гэтак жа эфектыўным, як праверка іх, мы павінны прызнаць, што сцвярджэнне аб тым, што доказ P = NP даб'юцца гэта невялікае перабольшанне.

4
дададзена

Справа ў тым, што, калі P = NP, то будзе існаваць універсальны алгарытм (дастасавальна не толькі да канкрэтных тэарэма), што б знайсці доказ у паліномны час у даўжыні доказы. Найбольш важныя вынікі маюць «малыя» доказы, па меншай меры, адпаведныя вызначаная мова, у тым сэнсе, што праверка доказаў, безумоўна, магчыма. Такім чынам, кошт знаходжання доказы, г.зн. вырашыць тэарэму, з'яўляецца полі (магчыма) = здзяйсняльна.

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

4
дададзена
<�Я> «і маё доказ памеру ...» </я> не пазначаны ў якасці ўваходных дадзеных для вашага алгарытму.
дададзена аўтар Billy ONeal, крыніца
Рыкі, ваш алгарытм будзе <�б> не заўсёды спыніць. Выберыце аксіёмам быць ZFC і ваша прапанова будзе гіпотэза кантынууму. Ваш алгарытм будзе працаваць вечна, бо няма ніякіх доказаў альбо СН або $ \ атр $ CH ад ZFC, не кажучы ўжо адзін, які з'яўляецца полиномом па даўжыні CH! Што датычыць другога пытання: калі памер $ | р | $ з доказы $ р $ полінаміяльна $ N $, то $ | р | \ Leq \ падпіраць {0 \ Leq я <�да} \ сума a_i \ CDOT п ^ {b_i} $; у $ a_i $ каэфіцыенты і $ b_i $ з'яўляюцца тлумачальнікі (я напісаў «каэфіцыенты і індэксы у якасці ўваходных дадзеных»).
дададзена аўтар Billy ONeal, крыніца
Я хацеў бы таксама дадаць, што любы алгарытм, які заўсёды спыняецца абавязкова патрабуецца веданне каэфіцыентаў карэктара памеру як дадатковы ўваход (алгарытм ў адказ Рыкі можа не спыніць, таму яго не трэба каэфіцыенты як ўваходы).
дададзена аўтар Billy ONeal, крыніца
Дэвід, алгарытм будзе працаваць толькі тады, калі існуе доказ паліномны памеру. Калі адзін не зрабіў, то алгарытм проста не спыніць, але вы ніколі не ведаеце розніцу паміж «ніколі не скончыцца» і «павінен працаваць толькі крыху больш часу». Такім чынам, алгарытм будзе бескарысны без папярэдняга веды доказы памеру. Ён па-ранейшаму здаецца, што наступствы ў цяперашні час празмерна разадзьмутымі.
дададзена аўтар Billy ONeal, крыніца
Адам, пераважная большасць доказаў, знойдзеных людзі кароткія. Там жа часам гіганцкае 100-старонкавае доказ, але калі пераважная большасць доказаў можа быць згенеравана машынай, то ўплыў на матэматычнай практыцы будзе вялікім.
дададзена аўтар arsmath, крыніца
«Вылучыце аксіёмам быць ZFC і ваша прапанова будзе кантынуум-гіпотэза» і маё доказ памеру, як ...? Пасля таго, як ён правярае ўсе магчымыя доказы дадзенага памеру, ён спыніцца на «няма кароткага доказы» (калі ZF адпавядае).
дададзена аўтар George Bora, крыніца
Reeaallyy? Тады што п ў «задачы (2n): = '. Існуе доказ даўжыні п, што першапачатковае зацвярджэнне ілжыва» і «задачы (2n + 1): =« Існуе доказ даўжыні п, што арыгінальнае зацвярджэнне дакладна. "? Ён упэўнены, здаецца, доказ памеру для мяне.
дададзена аўтар George Bora, крыніца
Што такое «каэфіцыенты карэктара памеру ў»? Алгарытмы, у тым ліку шахты, узяць памер Доказы як дадатковы ўваход і заўсёды спыніць, з адказам «True», «False», або «не кароткага доказы» (ці «супярэчлівасці»).
дададзена аўтар George Bora, крыніца

Не, таму што калі ёсць такі клас, то ваша сістэма не мае якіх-небудзь формул з зменнымі,

,

«Ці ёсць нейкі трук для павароту відаў вынікаў матэматык клапоціцца аб в»
клас, што Вы хацелі да спытаць-пра тып?

Yes,

problem(2n) := "There is a proof of length n that the original statement is false,"
problem(2n+1) := "There is a proof of length n that the original statement is true,"

2
дададзена
Рыкі, ці ёсць шанец, што вы маглі б паказаць мне на паперы на «Не, таму што" частка? Акрамя таго, я думаю, вы не зразумелі запытаную «трук» - алгарытм вы сапраўдныя творы толькі тады, калі мы ўжо ведаем, што праблема задавальняе умовам (1) + (2) + (3). Пад «трук» я меў на ўвазе спосаб пераўтварэння адвольных праблем агульнай матэматычнага цікавасці да праблем, якія задавальняюць умове (1) + (2) + (3) - альбо доказ таго, што нічога падобнага не можа існаваць (што, здаецца, што ў першая частка вашага адказу кажа, хоць я быў бы ўдзячны за дадатковыя тлумачэнні). Дзякуй!
дададзена аўтар Billy ONeal, крыніца
(Працяг вышэй) Для ўсіх зыходных задач, {задача (п): п у N} ўяўляе сабой сямейства праблем, якія finitistically триггерные, такім чынам, што (калі ёсць сістэма можа працаваць з картэжам, то) кожны сапраўдны экзэмпляр мае доказ якога даўжыня абмежаваная полиномом п, і (калі наша сістэма сумесная, то) не ілжывы асобнік не мае такое доказ. Гэтыя праводзіць незалежна адзін ад аднаго нічога зыходная задача можа ці не можа задаволіць.
дададзена аўтар George Bora, крыніца
Не, таму што :-) гэта занадта проста, каб была папера на ім. Возьме лагічную аксіёму, замяніць формулу, па меншай меры адной зменнымі ў ім для кожнага з атамаў, а затым працягваць выкарыстоўваць замену, каб змяніць зменныя. Зрабіце гэта калі заўгодна шмат разоў, то рабіць тое, што будзе зроблена ў звычайным доказе асобніка праблемы, ці гэта адмаўленне. Гэта паказвае, што для ўсіх п, калі асобнік праблемы дазволім, то ёсць колькі заўгодна доўгія доказы, таму, у прыватнасці даўжыня доказы не будзе абмежаваная зверху полиномом п. (Працяг ніжэй)
дададзена аўтар George Bora, крыніца