{"id":284,"date":"2008-11-24T09:41:23","date_gmt":"2008-11-24T08:41:23","guid":{"rendered":"http:\/\/penszko.blog.polityka.pl\/?p=284"},"modified":"2008-11-24T09:41:23","modified_gmt":"2008-11-24T08:41:23","slug":"widze-cie-skarbie","status":"publish","type":"post","link":"https:\/\/blog.polityka.pl\/penszko\/2008\/11\/24\/widze-cie-skarbie\/","title":{"rendered":"Widz\u0119 ci\u0119, skarbie"},"content":{"rendered":"

<\/a>W roku 2000 poczciwy saper<\/em> zosta\u0142 „wpl\u0105tany” w matematyk\u0119 wy\u017csz\u0105, a \u015bci\u015blej w teori\u0119 algorytm\u00f3w. Angielski matematyk Richard Kaye opublikowa\u0142 na \u0142amach kwartalnika Mathematical Intelligencer<\/em> artyku\u0142 „Saper jest NP-zupe\u0142ny”. W\u0142a\u015bciwie nic szczeg\u00f3lnego, bo publikacji naukowych dowodz\u0105cych przynale\u017cno\u015bci jakiej\u015b gry lub \u0142amig\u0142\u00f3wki do okre\u015blonej klasy problem\u00f3w matematycznych powstaje niema\u0142o. W tym przypadku chodzi\u0142o jednak o gr\u0119 powszechnie znan\u0105 i popularn\u0105, a ponadto natychmiast zwr\u00f3cono uwag\u0119 na\u00a0zwi\u0105zek tego tematu z zagadnieniem P-NP\u00a0– jednym z siedmiu, za rozwi\u0105zanie kt\u00f3rych hojni Amerykanie z Instytutu Claya ufundowali w tym samym roku (nie przeczuwaj\u0105c kryzysu:)) po milionie dolar\u00f3w. P\u00f3\u017aniej w paru popularnych artyku\u0142ach pad\u0142y nawet ryzykowne stwierdzenia, \u017ce korzystaj\u0105c z sapera<\/em> \u0142ebski matematyk amator mo\u017ce zgarn\u0105\u0107 fortun\u0119.<\/p>\n

M\u00f3wi\u0105c w skr\u00f3cie, problem obliczeniowy jest klasy P, je\u015bli potrafimy go rozwi\u0105za\u0107 za pomoc\u0105 komputera. Je\u015bli natomiast nie umiemy tego zrobi\u0107 (co nie znaczy, \u017ce nie jest to mo\u017cliwe), bo komputer wcze\u015bniej by si\u0119 rozsypa\u0142 ze staro\u015bci ni\u017c zako\u0144czy\u0142 prac\u0119, w\u00f3wczas nale\u017cy do klasy NP, ale pod jednym warunkiem: je\u017celi kto\u015b poda rozwi\u0105zanie, to korzystaj\u0105c z komputera mo\u017cna sprawdzi\u0107, czy jest w\u0142a\u015bciwe.<\/p>\n

Problem za milion dolar\u00f3w sprowadza si\u0119 do rozstrzygni\u0119cia zagadnienia, czy obie klasy, P i NP, s\u0105, wbrew pozorom, identyczne, czy te\u017c\u00a0– co bardziej prawdopodobne\u00a0– nie. Okazuje si\u0119, \u017ce najwygodniej (co nie znaczy, \u017ce \u0142atwo) tego dokona\u0107 za pomoc\u0105 jakiego\u015b problemu NP-zupe\u0142nego, czyli np. saperowego, bowiem jest to taki problem, kt\u00f3rego rozwi\u0105zanie za pomoc\u0105 komputera jest r\u00f3wnoznaczne z udowodnieniem mo\u017cliwo\u015bci uporania si\u0119 komputerowo z wszystkimi problemami NP. Ca\u0142a sztuka sprowadza si\u0119 do znalezienia odpowiedniego algorytmu.
\nWypada jeszcze doda\u0107, na czym polega problemowo\u015b\u0107 sapera<\/em>. Ot\u00f3\u017c nie wi\u0105\u017ce si\u0119 ona bezpo\u015brednio z rozgrywk\u0105, ale z rozk\u0142adem element\u00f3w na planszy. Konkretnie chodzi o wykazanie niesprzeczno\u015bci uk\u0142ad\u00f3w min i cyfr.<\/p>\n

Zanim zaczn\u0105 Pa\u0144stwo planowa\u0107, na co warto roztrwoni\u0107 nagrod\u0119 za rozwi\u0105zanie dzi\u0119ki saperowi<\/em> problemu P-NP, proponuj\u0119 pog\u0142owi\u0107 si\u0119 nad ostatni\u0105 \u0142amig\u0142\u00f3wk\u0105 saperow\u0105 (skarbow\u0105) w serii podminowanych („zaskarbionych”) wpis\u00f3w.<\/p>\n

Istnieje sporo mniej lub bardziej zakr\u0119conych odmian zada\u0144 polegaj\u0105cych na odkrywaniu skarb\u00f3w, kt\u00f3rych po\u0142o\u017cenie zaszyfrowane jest cyfrowo w saperowy spos\u00f3b. Do mniej znanych, a bardziej zakr\u0119conych, nale\u017c\u0105 skarby obserwowane<\/em>.<\/p>\n

\"\"<\/a><\/a><\/p>\n

Ka\u017cda cyfra oznacza w ilu polach, stykaj\u0105cych si\u0119 z polem z cyfr\u0105 bokiem<\/strong>, jest skarb.
\nPonadto:
\n– z ka\u017cdego bia\u0142ego pola bez skarbu wida\u0107, patrz\u0105c w rz\u0119dzie lub kolumnie<\/strong>, przynajmniej jeden skarb;
\n– \u017caden skarb nie „widzi” innego skarbu;
\n– szare kratki (tak\u017ce te z cyframi) ograniczaj\u0105 pole widzenia<\/em>.\u00a0\u00a0 Do widzenia.<\/p>\n","protected":false},"excerpt":{"rendered":"

W roku 2000 poczciwy saper zosta\u0142 „wpl\u0105tany” w matematyk\u0119 wy\u017csz\u0105, a \u015bci\u015blej w teori\u0119 algorytm\u00f3w. Angielski matematyk Richard Kaye opublikowa\u0142 na \u0142amach kwartalnika Mathematical Intelligencer artyku\u0142 „Saper jest NP-zupe\u0142ny”. W\u0142a\u015bciwie nic szczeg\u00f3lnego, bo publikacji naukowych dowodz\u0105cych przynale\u017cno\u015bci jakiej\u015b gry lub \u0142amig\u0142\u00f3wki do okre\u015blonej klasy problem\u00f3w matematycznych powstaje niema\u0142o. W tym przypadku chodzi\u0142o jednak o gr\u0119 […]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/284"}],"collection":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/comments?post=284"}],"version-history":[{"count":0,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/284\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/media?parent=284"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/categories?post=284"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/tags?post=284"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}