Křížovka


Original: http://thue.stanford.edu/puzzle.html

( Tato stránka byla dříve s názvem “ Teorie Puzzle “ , ale vyvinul se zaměřit na jeden puzzle , whence novým názvem jako ze 17. prosince 2012. Také jsem právě přepracovala puzzle zmírnit matematický jazyk, v naději, že osloví širší publikum . )

PUZZLE

Každý jazyk má svou vlastní představu o tom, co představuje “ slovo . “ v
Angličtina “ hořčice “ jeslovo, zatímco “ moutard “ není . Ve francouzštině je
naopak.

Toto puzzle se týká nedávno objeveny rukopis nalezený v jeskyni
v nedávno osvobodil zemi Dolní Elbonia . Zdá se, že
být napsán v jazyce, tak zvláštní, že se lingvisté studují ji
nazvali jej Gobblidook . Má pouze dvě písmena , budu jim říkat
a b, ačkolipuzzle by bylo možné zobecnit na více písmen .

Zatím každé slovo se setkal v rukopise bylastejná
délka, když lingvisté jsou zbývající ticho , co to
délka je , dokud se přesvědčili sami sebe, že není jiné délky
se vyskytuje v rukopise .

Mají však zveřejněny určité zákonitosti , které byly pozorovány v
část rukopisu mají studovali tak daleko.

1. . Každé slovo, které používá pouze jeden dopis byl viděn v
rukopis . Pouze s písmeny A a B, které prostě znamená, že
že jsem pozoroval dvě slova aaa …a BBB … b někde v
rukopis .

2 . Jestliže jeden tvoří křížovky bez černých čtverců taková, že
slova, napříč a dolů , to vše bylo vidět v rukopise , pak
slovo tvořené písmeny běží dolůúhlopříčka z levého horního rohu
na pravé dolní části lze nalézt také v rukopise .

3 . Pokud člověk začne tvořit jakékoliv slovo píše dva dopisy, ve dvou
Slovo pozice , lze vždy najít slovo v rukopisu , který má
tyto dva dopisy na těchto dvou místech .

Tak tady jepuzzle . S vědomím, že lingvisté potvrdily 1-3
na základě toho, co jsem zkoumal tak daleko , to existuje slovo ,
stejné délky , jako ty, které jsem zjistil , že se dosud
se setkal v rukopise , nebo jste se nyní vidět všechny možné
Slovo dané délky v rukopisu ?

Slova až do určité délky ,odpověď je :druhý . Chcete-li zobrazit
Proto budete potřebovat přečíst historii puzzle .

Nejjednodušší případ je, když slova jsou konečné . Uvidíme, jestli můžete dokázat,
to sami .

Poněkud těžší případ je, když každé slovo pokračuje věčně . ( Tyto
lingvisté byli vyškoleni nabírat rychlost , protože si ani slovo ,
výdaje pouze polovinu tak dlouho, při pohledu na dané písmeno , jako tomu bylo
při pohledu na předchozí písmeno , jinak by se zavěsil na
První slovo, které se podíval na . )

Případ , že zatím není známo , je-li písmena slova jsou
tak nahuštěné jako body na přímce . To znamená, že každý bod na
vedení o délce jedné noze říci má svůj vlastní dopis . To je mnohem více
hustý než slova, které pouze jde donekonečna , kde každé písmeno lze
ještě říkají tři milimetry prostoru pro sebe .

I když se to může zdát nepředstavitelně hustá , tady je jeden způsob, jak myslet na to .
Vzhledem k tomu,abeceda má pouze dvě písmena jakoslovo může být definován
jako stejná věc jako sadu těchto bodů na trati , na které
Dopisje psán . Bodů, ve kterých jepísmeno b jsou písemné
body nejsou v této sadě .

( Co je tosoubor , ptáte se? Oh , ne , že učí, že ve škole to
dny ? Možná , že je todobrá věc . )

V této super- hustý případě, že puzzle je nevyřešený.

( Následující překlady z mého “ křížovka „, která představuje otázku, zda každý T1 comonoid je diskrétní najdete na uvedených stránkách .

( Aktualizace 18.prosince 2012 : Tato stránka má nyní

Slovinský překlad s laskavým svolením Gasper Halipovich .

(Update 09.08.2012 :otázka “ je každý T1 comonoid diskrétní “ má nyní

Polský překlad s laskavým svolením Valeria Aleksandrova .

Jak můj polský je neexistující jakékoli řešení v tomto jazyce budou muset být
přeloženy do angličtiny .

(Update 10.06.2012 : Tato stránka má nyní

Ukrajinský překlad s laskavým svolením Vlad Brown , viz též zde .

Puzzle ještě unsolved po několika 17 let. Nové puzzle : do kolika jazyků
budestrana puzzle byly přeloženy do dobyhlavní puzzle je vyřešen ?

( Aktualizace 02.03.2011 : Tato stránka má nyní
Běloruský překlad s laskavým svolením Martha Ruszkowski .
Puzzle stále nevyřešené po asi 16 letech. Doufám, že to neznamená, že budu teď
začít přijímat řešení v běloruštiny . )

PUZZLE 1.5 : Aktualizace 16.ledna 2004

Stále žádné události . Cenu ve výši $ 2000 pro řešení tohoto puzzle
zůstává uncollected . No tak , lidi , tento problém asi křížovky
puzzle je snadno stát , tak to určitě nemůže být tak těžké , to může ?

Mluvil jsem o tomto problému a jeho pozadím na tento měsíc výroční AMS
setkání ve Phoenixu , AZ , v relaci na “ Mnoho životů mřížových
Teorie . „Diskuse byla vhodně naplánován hned po Dana Scott
mluvit , protože oba jsme se zabývali otázkou, jak se
Vyrábíme komplexní kartézsky uzavřené kategorie , něco
domáckého průmyslu v těchto dnech . Například Martin Escardo , Alex Simpson ,
a Jimmy Lawson oznámil před třemi dny ( 13.ledna ), jejich práce “ Porovnání
kartézsky uzavřená kategorie ( core ), kompaktně generovaných prostorů “ ,
k dispozici na adrese
http://www.dcs.ed.ac.uk/home/als/Research/comparing.pdf ,
která zkoumá různé odnože Kelleyho původní představě
kompaktně generovaných Hausdorffovy prostory , které dodá homotopy s tím, co
Kelley považován za velmi výhodné kategorii .

Vaughan Pratt
[email protected]

PUZZLE 1.5 ( jako z 18. dubna 2003).

Tam byly žádné pozoruhodné události týkající Puzzle 1.5
minulý měsíc . Vypadá 18.dubna budeposlední aktualizace nato
puzzle , dokud někdo má nějaký pokrok hlásit ! Já bych byl v plánu
spuštění nové puzzle série číslovány 2.x , ale Tiqit začala
konzumují příliš mnoho svého času v poslední době , takže to bude muset počkat .

Zde je opětprohlášení o puzzle , s drobnou formulační změnou v
Podmínky sad sad místo predikátů na sad pro příčinu
odrůda .

Nechť D jemnožina podmnožin množiny A s těmito třemi vlastnostmi .

( i ) D obsahuje i prázdnou množinu .

( ii ) Nechť C je nějaký soubor dvojic ( a, b ) , a, b v A , taková, že pro všechny a v
, Množiny { b | ( a, b ) je v C } a {b | ( b , a) je v C } jsou v D. Pak
{ b | ( b , b ) je v C } je v D.

( iii ) ( T1 ) V případě jakýchkoli dvou různých prvků a, b A, D obsahuje sadu
obsahující, ale ne b , a další , který obsahuje B, ale ne.

Sada D se skládá ze všech podskupin A zřejmě splňuje ( i) – ( iii) .
Má někdo jiný soubor podmnožin A to tak ?

Podmínky ( i) – ( ii ) definovat pojem comonoid , zatímco podmínka ( iii )
vyjadřuje T1 majetku , který je definován jako topologických prostorů .
Otázkou je ekvivalentní s dotazem, zda každý T1 comonoid je diskrétní .
To platí pro dva zvláštní případy : počitatelná T1 comonoids , a T1
comonoids , že forma směřovat CPO ( DCPOs ) . Na druhé straně není
v případě, že každý T1 topological prostor je diskrétní , nebo topologie by
býtvelmi odlišný předmět .

Nejnovější pozoruhodné pozorování se vynořit z teorie okrajem
diskuse tohoto problému je Mark Aujus ‚ příklad comonoid
představuje přirozená čísla N standardně objednané spolu s
Další bod nucen být menší nebo roven sup N
aniž by byla omezena , že je menší nebo roven jakýkoliv specifický přírodní
číslo . To jedruh objednávky informací není representable s
obyčejný poset .

vidět

http://boole.stanford.edu/pub/comonoids.pdf

Pro mé práce na toto téma prezentované na Coalgebraic metody v CS
workshop koná 5 až 6 04 ve Varšavě . Viz níže pro informace o
cena pro řešení tohoto problému .

7. března , 18. dubna 2003 : Žádné komentáře v tomto období .
( Dříve obsahu řídké 7.března vysílání smazána . )

28.února 2003 : PUZZLE 1.5

Ne zvýšit tento týden . Zde však jeupřesnění cenu
Struktura tvrzení TCD = “ Všechny T1 comonoids jsou diskrétní . “

Důkaz, že TCD je v souladu s ZFC bude vydělat $ 1000. Důkaz, že
jeho negace ~ TCD je v souladu s ZFC bude vydělávat $ 500 a více, pokud
pravděpodobné, aplikace pro všechny nondiscrete T1 comonoids může být
prokázána .

Podrobnější informace o měření vzdálenosti od ZFC , např. představení
implikace v obou směrech mezi TCD nebo ~ TCD a některé
dobře známý axiom známo, že je nezávislá na ZFC , bude vydělávat další
částky v závislosti na axiomy použité .

Částky pro tyto dílčí výsledky budou vyřazeny z celkového počtu . tedy
důkaz, že ~ TCD je v souladu s ZFC následuje důkaz ~ TCD v
ZFC by se rozdělit na $ 2000 pro 500 dolarů na první a $ 1500 až
druhé . Pokud se v jiném pořadí všakcelý 2000dolar by samozřejmě
jít na dokladu o ~ TCD .

Vaughan Pratt

21.února 2003 : PUZZLE 1.5

Ok , poslední přírůstek za chvíli : jedna 500 dolarů přináší jackpot se
2000 dolar . To zůstane tam, dokud někdo řeší hádanku .

Vaughan Pratt

14.února 2003 : PUZZLE 1.5

V určitém okamžiku budu muset zastavit , ale v současné době
přírůstek je opět 500 dolarů. Puzzle 1.5 má nyní 1500 dolary na hlavu .

Všechny definice , námitky , atd. z předchozích hádanek nadále platit .

Vaughan Pratt

07.02.2003 : PUZZLE 1.5 ( stále )

Přečtěte si mé rty : žádné nové hádanky , dokud je to jedna vyřešen .

Cena je nyní 1000 dolar .

Mějte na paměti, že načasování prvního správný vstup je určen
kdy je vyslán na [email protected] , ne -li vyřešit
to , nebo když ho poslat na mě .

Vaughan Pratt

PS ( přidáno 10.února ) : Chcete-li uložit nováčky bolest smontování Puzzle 1.5
z jeho účtu zlomkovité níže , tady jesoběstačný údajů .

Nechť D jepredikát na moci nastavit 2 ^ A s těmito třemi vlastnostmi .

( i ) D platí A a prázdné množiny .

( ii ) Nechť C je každá binární predikát natakové, že pro všechnyv A , D platí
obou { b | C ( a, b ) } a {b | C ( b , a) } . Pak D je také držitelem z { b | C ( b , b ) } .

( iii ) V případě jakýchkoli dvou odlišných prvků a, b A, D má z nějaké podmnožiny
Obsahující , ale ne B a jeden obsahující b , ale ne.

D = TRUE evidentně splňuje ( i) – ( iii ) . Má jakýkoli jiný predikát o 2 ^ A ?

31.leden 2003 : PUZZLE 1.5

Má tam existovat nondiscrete T1 binární comonoid ? ( Definice pod . )

První správně a zdravě odůvodněné odpovědi zveřejněny na
[email protected] vyhraje svou zadavatele USA 500 ​​dolarů .

Definice .

1. . Slovo nad abecedou S jedvojice ( A, f) , kdejesoubor s názvem
* délka * slovo , a f jefunkce f : A – > S dává
písmena slova . Příklad . S = 2 = { 0,1 } , A jemnožina reálných čísel ,
a f : A – > S je mapování funkce rationals 1 a irrationals na 0 .

2-4 . Pokud jde o puzzle 1,4 ( což je uvedeno níže ) .

Poznámka . Jako dva lidé poznamenal , “ nekonečný slovo “ , jak je definován v minulém týdnu puzzle byla přísně vzato “ countably nekonečné slovo . “ Existují i ​​další nekonečné množiny , než přirozených čísel . Jak již bylo uvedeno , křížovka existence je nezávislá na pořadí slov pozic :slovník D má křížovka právě když D “ má křížovku , kde D ‚ je odvozen od vývoje by řekl vymění první dvě písmena každého slova . Solution Marka a mělo mást 1.4 se proto vztahuje na jakékoliv slovo z počítání délky a , což znamená slovo ve výše uvedeném smyslu , pro kterýjespočetná set, tj. souboru v one- to-one korespondence s množinou N přirozených čísel .

Proto tento týden puzzle žádá o prodloužení výsledek Marka slov délky přísně delší než N , tj. nespočetně dlouhých slov .

Tip . První vyřešit problém A do množiny reálných čísel . Jakékoli řešení, které funguje pro tento příklad nespočetné délky je téměř jistě bude pracovat pro libovolnou délku .

Slovo o délce R nad { 0,1 } jefunkce z R do 2 . To jetotéž, jako podmnožina R , který si můžete představit jako tečky podél reálné osy , jeden bod za skutečný v podskupině , zcela bez omezení , jak na hustotě nebo distribuce . Můžete si dát žádné tečky nebo tečky , všude podél čáry nebo tečky jen na celá čísla , nebo jen na racionální , atd.

Slovník slov o délce R je tedy nic více nebo méně než soubor sad reálných čísel , jako je například { { 1,4 , 3 } , { 2,78 , 9,1 } } ( ale samozřejmě , že je to pouzekonečný příklad ) . Equivalently jesada libovolně tečkovanými čarami .

Křížovky pak činí bodů v rovině tak, že pro každé svislé nebo vodorovné čáry , tečky na tomto řádku jsou z nějakého slova ve slovníku . Problém se ptá přímky y = x : v případě, že body podél ní vždy tvoří slovo ze slovníku , je zdeslovo ( podmnožina R ), kteréslovníku můžete vynechat ?

24.leden 2003 : PUZZLE 1.4

Pro slovníků s nekonečnými slovy , to tam existovat nondiscrete T1
binární comonoid ? ( Definice pod . )

První správně a zdravě odůvodněné odpovědi zveřejněny na
[email protected] vyhraje svou zadavatele US $ 90 .

Definice .

1. . Nekonečné slovo jenekonečná posloupnost a0 , a1 , a2 , … dopisů .
Příklad : 31415926535 … jenekonečná posloupnost , jehož písmena jsou od
abeceda { 0,1,2 , … , 9 } .

2 . Slovník slov dané délky na dané abecedě je
* diskrétní * pokud obsahuje každé slovo této délky přes tento abecedy .
Příklady : Pouzeslovník na pravé straně je diskrétní ,jeden na
vlevo chybí slovo 00 .

011 0011
101 0101

3 . * Comonoid * za dané abecedě jeslovník slov všechny
stejné délky , která zahrnuje všechny stálé slova , a mají
vlastnost , že pro každé křížovky , jejichž řádky a sloupce jsou ve
slovník , jeho hlavní diagonále je také ve slovníku . ( Viz Puzzle
1.2 příklady . )

4 . Binární slovník D je T1 -li pro každou dvojici a, b ​​bodů tam
jsou dvě slova v D jako v bodě A , jedno slovo je 0 adruhý 1 ,
zatímco b je tonaopak . Příklad :slovník na
odešel se slovy, 01 , 10 a 11 ,

011 011
101 001

Je T1 , protože máme jen dva body na starosti , což odpovídá
první a druhé řady , a v první slovo ( sloupec) máme 0
pak 1 , zatímco v druhém máme 1 pak 0 , tvořící 2×2
šachovnice . Jeden na pravé straně , se slovy 00 , 10 a 11 , není
T1 od druhé řady je < =první řádek , ekvivalentně neexistuje
“ šachovnicový “ vzor dvou 0s a 1s dva kdekoliv v těchto dvou
řádky .

Vaughan Pratt

Binární samozřejmě znamená, že nad abecedou { 0,1 } . Takže Puzzle 1.2 byl o konečných binárních comonoids . T1 vlastnost zajišťuje, že tam může být žádné dva body a, b ​​taková, že buď a < = b nebo b < =srovnání kousek po kousku . Vzhledem k tomu, konečné T0 comonoids jsou jen dílčí objednávky , posílení T0 T1 zabraňuje netriviální pořadí , aneuspořádané sada umožňuje všechny možné střihy a odtud každý konečný T1 binární comonoid je diskrétní . Puzzle se ptá, zda to se vztahuje i na nekonečné comonoids .

Význam . Topologické prostory mohou být T1 ( jen triviální = diskrétní pořadí ) , aniž by byl topologicky triviální = diskrétní topologie .

Kompletní dílčí objednávky ( CPO ) , na druhé straně , podle definice získat žádné topologické struktury , které by mohly mít z jejich objednávky struktury . CPO ječástečné uspořádání X každý řídil set, z nichž jenejméně horní spojený ( v X , ale ne nutně v A ) . (Podmnožinaz částečně uspořádaná množina X se nazývá * směřuje * pokud je neprázdná a pro každou dvojici a, b ​​veexistuje c vtakové, že< = c a b < = c Minipuzzle : . Jakýkoli konečný režie soubor musí mít maximální prvek a odtud všichni konečný režii nastavímítnejméně horní spojený nejen , ale obsahují ji . Proto každý konečný částečná objednávka je automatickyCPO . ) Pokudalespoň horní hraniceo režii množiny A není a , možné pouze pro nekonečnou a ,topologie Scott v tomto CPO zakazuje řez oddělujícíod a , to znamená, že trvá na bytí hranici A.

Jediné směřující sady T1 CPO ( jeden , jehož pořadí je právěidentita vztah=) jsou singletons , a jakoCPO proto nemůže mít netriviální topologické struktury .

Takže to, co jsme tady opravdu ptá , je , že nekonečné comonoids jít cestou topologických prostorů nebo CPO , pokud jeT1 podmínka uložená ? Mohou mít strukturu bez pořadí , nebo se musí ztratit to všechno ?

ŘEŠENÍ NA PUZZLE 1,4 , Mark ( aujus_1066 AT yahoo.com ) , v 6h 10m.

Lemma : Je-li D jeT1 binární comonoid s ( countably )
nekonečné slova , potom pro všechny konečné předpony p , existuje
existuje slovo w D s předponou s. .

Důkaz : Index postoje slov počínaje 1. . nechat
t ( i , j ) jeslovo v D , jehož i- tý pozice je 1 , a jejichž
j – tého pozice je 0 . Takovéslovo je zaručeno, že bude v
D , protože T1 vlastnosti . Nechť k je délka p ,
a nechal jsem seindex od 1 do k. . Definujte m ( i , k)
je A z { t ( i , j ) : 1 < = j < = k , j = i ! } . Pak m ( i , k)
je v D , protože D je uzavřen pod konečný A , a
i – tý polohy m ( i , k) je 1 , zatímco ostatní pozice
mezi 1 a k je 0 . Nyní , ať w je OR
{ m ( i , k ) : 1 < = i < = k , i-tá pozice p je 1 } . pak
pro 1 < = i < = k ,i-tá pozice W je 1 právě tehdy, když
i – tý polohy p je 1 . Proto w má předponu p , a
w je v D , protože D je uzavřená na konečný OR. QED

Lemma : Nechť D jeT1 binární comonoid s ( countably )
nekonečné slova , a ať W jelibovolná ( countably )
nekonečné slovo . Potom w je v D.

Důkaz : Máme sestrojit ( symetrický ), křížovky , jejíž řádky
a sloupce jsou v D , a jehož úhlopříčka je w .
Proto , podle comonoid majetku , w bude v D.

Nechť r ( i ) jei- tý řádek ( i sloupec ) z
křížovky , a nechte r ( i) _j býttrochu na j -tého
pozice r ( i) . Construct křížovku takto :

r ( 1 ) : = slovo v D s předponou W_1 ,
r ( 2 ) : = slovo v D s předponou r ( 1 ) _2 w_2 ,
r ( 3 ) : = slovo v D s předponou r ( 1 ) _3 r ( 2 ) _3 w_3 ,

r ( n ) : = slovo v D s předponou r ( 1 ) _n r ( 2 ) _n … r ( n – 1 ) _n w_n ,

Je zřejmé, že o výstavbě ,úhlopříčka křížovky
je w , takže máme r ( i) _i = w_i za všechno, co jsem . Také , každý řádek
z křížovky je v D. Zbývá ukázat, že
křížovky je symetrická , která zaručí, že všechny
sloupce křížovky jsou také v D. Pro ​​1 < = i < n , r ( n ) _i jei- tý bit předponou r ( 1 ) _n r ( 2 ) _N … r ( n – 1 ) _n w_n , která je r ( i) _n . Tedy r ( n ) _i = r ( i) _n . QED Důsledek : Každý T1 binární comonoid s ( countably ) nekonečné slova je diskrétní . 17.leden 2003 : PUZZLE 1.3 Čtvercové Logické křížovky . Vzhledem k tomu,celé číslo n > 0 , asoubor D n-bitových
vektorů , je tamnxn křížovka , jejíž řádky a sloupce jsou všichni v D ?

Příklady ( n = 3 ) : D = { 101110 } : ne . D = { 001011100 } : ano , [ 100001011 ] .

Tento problém je buď NP- těžké nebo v P. za US $ 100, který a proč ?
Odpovědi na [email protected]

Vaughan Pratt

Mark vyřešit tuto hádanku ve prospěch NP – těžké na pouhých 82,5 hodiny , po hodně času stráveného “ se snaží dokázat, tento problém je v P o zobecňující hmotnost = 2 případ a najít “ rozšiřovat path‘ typu algoritmus a / nebo přesná charakterizace a la Hallova věta. “

… tady jeredukce z 3DM , které trvalo 5 minut zjistit,
ahodinu dokázat , v mém spánku -zanedbaný stav .

( Naštěstí pro Marka , že ne “ spát na to “ , protože Mike Robson dal elegantní snížení ze tří písmen čtvereční případě pouhé 3,5 hodiny později . ) Pokračování roztokem Marka , …

Vzhledem k tomu, 3n vesničany , láskyplně nazývané 1,2 , .., 3N, kde
První sex je od 1 do n ,druhý sex je od n +1 až 2n , a
Třetí sex je z 2n +1 na 3n , asoubor přijatelných triplings
pro ně , tvoří slovník se slovy délky 3n více
abeceda { 0,1 } takto . Slovník se skládá z jednoho slova
délky 3n za přijatelnou ztrojnásobila . Toto slovo má tři 1 je ,
které jsou umístěny na pozicích odpovídajících třem
Vesničané v tomto ztrojnásobila ( to je důvod, proč jsme se jich zeptal na
jejich jména dopředu ) .

Reklamace : Je3n x 3n náměstí křížovka kompatibilní
s tímto slovníkem tehdy a jen tehdy, pokud všichni vesničané mohou být
ztrojnásobil až přijatelně .

Důkaz ( pouze tehdy, když ) : první n řádky křížovce dát
přijatelné ztrojnásobení , že můžeme číst off . Vzhledem k tomu, že řádky
jsou ve slovníku , který obsahoval pouze přijatelné trojice ,
Jediné, co zbývá být prokázáno, že každý vesničan
se objeví přesně jednou v tomto roztoku . Ale každý sloupec je
slovník i , který má tu vlastnost, že v prvním
n bitů každého slova , je právě jedním 1 . Proto žádný vesničan
se může objevit dvakrát nebo vynechat z roztoku .

Důkaz (pokud je ) : Vzhledem k tomu, přiřazení starosty , to poskytuje
oddíl o všech 1 slovo , což znamená, žeslovník
je 1- pojistitelným , a tudíž crosswordable . Ve skutečnosti , protože
každý 1 pojistitelným slovník symcrosswordable , to znamená,
žeproblém najít symetrický čtvercový křížovky je
NP – úplný i . QED

Mark , jít do postele pro čtyři a půl hodiny , než jsem se
vstát , aby svou dceru do školy .

10.01.2003 , 21:00 GMT : PUZZLE 1.2

Úhlopříčka křížovka problém . Vzhledem k tomu,celé číslo n > 0 aslovník ( tj.
sada ) D n- bitové binární slova , včetně dvou stálých slova 00 … 0 a
11 … 1 , je tamnxn křížovka , jejíž řádky a sloupce jsou v D , ale jejichž
hlavní diagonále ( napříč a dolů) není v D ?

Příklady . D = { 000010100111 } : ano , diag [ 100010000 ] = 110 .
D = { 00,01,11 } : ne .

Tento problém je buď NP- těžké nebo v P. za US $ 70, který a proč ?
Odpovědi na [email protected]

Vaughan Pratt

Poté, co se lidé z různých “ her — systém “ hádat , který z NP- těžké nebo P bylo správné , Mark ( aujus_1066 na yahoo.com ), znovu byl první předložit správnou odpověď .

Je zajímavé porovnat Puzzle 1.1 a 1.2 na dobu do řešení oproti složitosti odpovědi . 1.1 se Mark 35 minut , zatímco 1.2 se ho 8 hodin 55 minut . Řešením 1.1 byldynamický programovací algoritmus podobný Floyd all- nejkratší trasy algoritmus nebo Cocke – Kasami – Younger ( CKY ) bezkontextové analýzy. Řešení na 1,2 bylo dokázat, žeproblém byl ekvivalentní s dotazem, zdaslovníku byla uzavřena pod AND a OR .

Hádám , že Puzzle 1.3 bude i nadále tento vzor : ještě těžší vyřešit , než 1,2 ( tak to bude více ) , ale s řešením, stejně jako krátké , jednoduché a zřejmé, při zpětném pohledu , jako jsou 1,2 a 1,1 . Budu rád, pokud někdo prokáže mě špatně na obtížnosti řešení.

Od : “ aujus_1066 “
Pro : [email protected]
Datum : so. 11.1.2003 05:54:55 -0000
Předmět: [ teorie – edge ] Re : Puzzle 1.2

Zde je pseudokódu pro O ( ( d ^ 3 ) * n ) algoritmus , kde
d jemohutnost slovníku D :

bool odpověď , found_or , found_and ;
bool w1 [ n ] , w2 [ n ] , w3 [ n ​​] , word_or [ n ] , word_and [ n ] ;

odpověď : = true ;
pro w1 v D dělat
__ Pro W2 v D dělat
_____ Word_or : = w1 | w2 , / / bitový nebo
_____ Word_and : = w1 & w2 , / / bitový a
_____ Found_or : = false ;
_____ Found_and : = false ;
_____ Pro W3 v D dělat
________ If ( w3 == word_or ), pak
___________ Found_or : = true ;
________ End if ;
________ If ( w3 == word_and ), pak
___________ Found_and : = true ;
________ End if ;
_____ End pro ;
_____ If ( ( found_or ) | ! | ! ( Found_and ) ), pak
________ Odpověď: = false ;
_____ End if ;
__ End pro ;
konec pro ;
návrat odpověď ! ;

V podstatě ,algoritmus testuje , pokud je slovník
je uzavřen pod “ bitového a “ a “ bitového nebo “ , a
pak se vracet “ ne “ , je-li a “ ano „, pokud tomu tak není.
Opírá se o následující tři lemmat :

Lemma 1 : Je-li D není uzavřen pod “ bitového a “ , pak
existujekřížovka , jejíž řádky a sloupce
jsou v D , ale jehož úhlopříčka není v D.

Důkaz : Nechť[ n ] a b [ n ] jsou dvě slova v D
tak, že A a B není v D. pak tvoří
křížovka c [ i ] [ j ] =[ i ] a B [ j ] . Každý řádek
c [ i ] [ * ] je buď b nebovšechny nulové slovo ,
v závislosti na tom, zda a [ i ] je 1 nebo 0 . Stejně tak ,
každý sloupec c [ * ] [ j ] je jedennebovšechny
nula slovo , v závislosti na tom, zda b [ j ] je 1 nebo 0 .
A konečně ,je diagonálnía b , které nejsou v D.

Lemma 2 : Je-li D není uzavřen pod “ bitového nebo “ , pak
existujekřížovka , jejíž řádky a sloupce
jsou v D , ale jehož úhlopříčka není v D.

Důkaz : Nechť[ n ] a b [ n ] jsou dvě slova v D
tak, že| b není v D. pak tvoří
křížovka c [ i ] [ j ] =[ i ] | b [ j ] . Každý řádek
c [ i ] [ * ] je buď b nebovšichni jedno slovo ,
v závislosti na tom, zda a [ i ] je 0 nebo 1 . Stejně tak ,
každý sloupec c [ * ] [ j ] je jedennebovšechny
jedno slovo , v závislosti na tom, zda b [ j ] je 0 nebo 1 .
A konečně ,je diagonální| b , které nejsou v D.

Lemma 3 : Je-li D je uzavřen pod “ bitového a “
a “ bitový nebo “ , pak to znamená, že pro všechny
křížovka , jejíž řádky a sloupce jsou všechny
D ,úhlopříčka křížovce je
i D.

Důkaz : To platí o kontrole pro n = 1 a n = 2 .
Pro n > = 3 , můžeme dokázat lemma indukcí .
Vymazání i – tý bit z každého slova v D ,
indukční hypotéza ukazuje diagonální s
jeho i -tý bit je odstraněna v D. To znamená, že jediný
způsobem, který plně úhlopříčka není v D , je-li
úhlopříčka s i-tého bitu převrácený v D.
To musí platit pro každé i. . Nyní , v případě, že diagonální
má dvě 0 a poté “ bitového a “ o mizerný
každý z nich je 0 je původní diagonální , a
tedy v případě, že úhlopříčky D. má dva 1 a poté
“ bitový nebo “ z obracející každý z těchto let 1
je původní diagonální , a tedy v D. Ale
od n > = 3 , musí dojít k některým z těchto dvou případů.

značka

Postscript ( podle Vaughan ) . Mark dokazuje Lemma 3 indukcí , což je v pořádku . Nicméně to vyvolává otázku , zda je nezbytné indukce . Následující důkaz zabraňuje indukci , a navíc funguje i pro slovníky s nekonečně mnoha nekonečně dlouhých slov , jen když je uzavřen pod AND a OR * jakékoliv * ( libovolný ) set slov . ( Tedy v případě, že slovník je nekonečný ,AND nebo OR jakékoliv nekonečné množiny slov ze slovníku musí být ve slovníku . )

Lemma 3 . Je-li slovník D je uzavřen pod libovolným AND a OR , a
obsahuje dvě konstantní slova 00 … 0 a 11 … 1 , pak nějaká křížovka
postavený z D má úhlopříčku také v D.

SLOVNÍK Předběžné zpracování úvahu.

Pro každé i v 1. .. n , D obsahuje minimální slovní m ^ i , který má 1 v poloze I .

Důkaz : Získat m ^ i jako A všechna slova w D s w_i = 1 . QED

( Vzhledem k tomu, 11 … 1 v D , jsme se nikdy nebudete muset tvořita prázdné množiny . )

Hlavním argumentem , ONE DIRECTION .

Nechť M [ 1 .. n, 1 .. n ] jekřížovka na D s úhlopříčkou slovo d ( d_i = M [ i , i ] ) .

Nechť E jeOR všech m ^ i , pro které d_i = 1 .

Cvičení . d < = e ( to znamená, že každý 1 D se objeví v e ve stejné poloze ) .

( Všimněte si, že e byla postavena ANDing a ORing slova D , takže musí být v D. )

Hlavním argumentem , jiným směrem .

To stačí ukázat, e < = d . Nechť e_j = 1 ; chceme ukázat d_j = 1 .

Pro nějaké k takové, že d_k = 1 ,j – tý bit m ^ k. musí být 1 ( podívejte se na
jak e byl postaven ) . proto

************************************************** *
* Každé slovo ve slovníku , který má 1 v * ( 1 )
* K postavení , musí mít v poloze 1 j i . *
************************************************** *

( Podívejte se, jak se m_k postavena . )

Vzhledem k tomu, d_k = 1 , M [k , k ] = 1 .

Ale pak M [ j , k ] = 1 (aktivace ( 1 ) až k- tý sloupec M ) .

Ale M [ j , j ] = 1 (aktivace ( 1) do j -tého řádku M ) .

To znamená, že d_j = 1 . QED

Vaughan

3.1.2003 , 21:00 GMT : PUZZLE 1.1

String – řezání problém . Vzhledem k tomu, pozitivní celá čísla k a d1 < d2 < … < dn ,
můžeprovázek nakrájíme na kousky K postupně ( tj. u K-1
kusy jeden po druhém ), tak, že každá z 2K- 1 kusů řetězce
se setkal na cestě má délku di pro nějaké i v 1. .. n ?

( Příklady: Pro 1 < 3 < 6 < 8 ,maximální možná k je 2 — začít s 6
a snížit na polovinu , čímž se získá 2 kusy — , ale zvyšuje až 3 , pokud se sníží na 8
7 — začít s 7 , uříznout 1 pak 3 , čímž 3 kusy . )

Další objasnění : každý z k- 1 řezy mohou být aplikovány na jakýkoli z
kusy řetězce získat tak daleko ( na rozdíl od pouze řezání kusy
z konce hlavního kusu ) .

Příklad : Pro 1 < 3 < 6 < 10 < 14 ,maximální možná k je 2 — začátek
s 6 a snížit na polovinu , čímž se získá 2 kusy — ale zvyšuje se až k = 6 , pokud 10
se sníží na 7 — začít s 14 , snížit na polovinu , čímž se získá dva 7 a poté řez
každý ze 7 let do 1 3 3 stejně jako v předchozím příkladu .

Za předpokladu, že čísla jsou psány v binárním formátu , zda je tento
Problém je NP-těžký , nebo v P ( to je určitě jedno nebo druhé ) .

Odpovědi na [email protected]

50 US $ za první důkladně odůvodněné správnou odpověď , jak soudil podle
přiměřené shoda teorie nejmodernější čtenářů .

Vaughan Pratt

První správné řešení ( s výjimkouchybějící koncové , pokud ne biggy ) byla podána během 35 minut Mark Aujus , aujus_1066 na yahoo.com . Zde je O Marka ( n3 ) algoritmus jako kódovaný v C pomocí “ wahchelc “ :

# include

# define ARRAYLENGTH 4
int d [ ARRAYLENGTH ] = { 1,3,6,8 } ;
int v [ ARRAYLENGTH ] ;

int main ( ) {
int k = 2 ;
int j1 , j2 ;
int i ;
bool answer = false ;
for ( i = 0 ; i < ARRAYLENGTH ; i + + ) {
v [ i ] = 1 ;
for ( j1 = 0 ; j1 < = i – 1 ; j1 + + ) {
for ( j2 = 0 ; j2 < = i – 1 ; J2 + + ) {
if ( ( d [ j1 ] + d [ j2 ] ) == d [ i ] )
if ( v [ i ] < v. [ j1 ] + v [ j2 ] ) v [ i ] = v [ j1 ] + v [ j2 ] ; } } if ( v [ i ] > = k)
answer = true;
}
return 0 ;
}

Mark zase složil výhru v první osobě, s cílem zlepšit řešení Marka na O ( n2) , které tvoří to, co Mark tzv. puzzle 1.5 , což je 1.15 v novém rozšířeném číslování dělá . To vyhrál Daniel Marx s roztokem , který se stěhoval J2 se jako j1 posunul zůstat co nejblíže k d [ J1 ] + d [ j2 ] ) == d [ i ] s cílem zachytit každý přesné rovnosti tam , aniž by ztrácet čas na páry J1, J2 , pro které d [ j1 ] + d [ j2 ] ) se radikálně liší od d [ i ] .

Comments are closed.