abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
včera 21:33 | Nová verze

Byla vydána nová major verze 1.8.0 open source systému pro filtrování nevyžádané pošty Rspamd (GitHub, ChangeLog). Z novinek lze zmínit nový framework selectors, optimalizaci modulu ClickHouse nebo vylepšení webového rozhraní.

Ladislav Hagara | Komentářů: 0
včera 18:44 | Bezpečnostní upozornění

Sabri Haddouche vytvořil stránku Browser Reaper, na které demonstruje zranitelnosti současných verzí webových prohlížečů Chrome, Safari i Firefox. Zveřejněné skripty dokážou zahltit nejen webové prohlížeče, ale v závislosti na nastavení, také celé operační systémy.

Ladislav Hagara | Komentářů: 8
23.9. 19:22 | Nová verze

Byla vydána verze 11.3 open source alternativy GitHubu, tj. softwarového nástroje s webovým rozhraním umožňujícího spolupráci na zdrojových kódech, GitLab (Wikipedie). Představení nových vlastností i s náhledy v příspěvku na blogu.

Ladislav Hagara | Komentářů: 0
22.9. 13:00 | Komunita

Do 30. října se lze přihlásit do dalšího kola programu Outreachy (Wikipedie), jehož cílem je přitáhnout do světa svobodného a otevřeného softwaru lidi ze skupin, jež jsou ve světě svobodného a otevřeného softwaru málo zastoupeny. Za 3 měsíce práce, od 4. prosince 2018 do 4. března 2019, v participujících organizacích lze vydělat 5 500 USD.

Ladislav Hagara | Komentářů: 98
21.9. 22:22 | Komunita

Společnost Purism představila kryptografický token Librem Key. Koupit jej lze za 59 dolarů. Token byl vyvinut ve spolupráci se společností Nitrokey a poskytuje jak OpenPGP čipovou kartu, tak zabezpečení bootování notebooků Librem a také dalších notebooků s open source firmwarem Heads.

Ladislav Hagara | Komentářů: 9
21.9. 20:33 | Nová verze

Společnost NVIDIA oficiálně vydala verzi 10.0 toolkitu CUDA (Wikipedie) umožňujícího vývoj aplikací běžících na jejich grafických kartách. Přehled novinek v poznámkách k vydání.

Ladislav Hagara | Komentářů: 0
21.9. 20:00 | Upozornění

Příspěvek Jak přežít plánovanou údržbu DNS na blogu zaměstnanců CZ.NIC upozorňuje na historicky poprvé podepsání DNS root zóny novým klíčem dne 11. října 2018 v 18:00. Software, který nebude po tomto okamžiku obsahovat nový DNSSEC root klíč, nebude schopen resolvovat žádná data. Druhým důležitým datem je 1. února 2019, kdy významní výrobci DNS softwaru, také historicky poprvé, přestanou podporovat servery, které porušují DNS standard

… více »
Ladislav Hagara | Komentářů: 11
21.9. 15:55 | Pozvánky

Spolek OpenAlt zve příznivce otevřených řešení a přístupu na 156. brněnský sraz, který proběhne v pátek 21. září od 18:00 v restauraci Na Purkyňce na adrese Purkyňova 80.

Ladislav Hagara | Komentářů: 0
21.9. 13:22 | Nová verze

Alan Griffiths z Canonicalu oznámil vydání verze 1.0.0 display serveru Mir (GitHub, Wikipedie). Mir byl představen v březnu 2013 jako náhrada X serveru a alternativa k Waylandu. Dnes Mir běží nad Waylandem a cílen je na internet věcí (IoT).

Ladislav Hagara | Komentářů: 0
20.9. 22:00 | Nasazení Linuxu
Stabilní aktualizace Chrome OS 69 (resp. Chromium OS), konkrétně 69.0.3497.95, přináší mj. podporu linuxových aplikací. Implementována je pomocí virtualizace, a proto je tato funkce také omezena na zařízení s dostatkem paměti a podporou hardwarové akcelerace, tudíž nejsou podporovány chromebooky s 32bitovými architekturami ARM, či Intel Bay Trail (tzn. bez Intel VT-x).
Fluttershy, yay! | Komentářů: 6
Na optické médium (CD, DVD, BD aj.) jsem naposledy vypaloval(a) data před méně než
 (14%)
 (14%)
 (20%)
 (23%)
 (24%)
 (4%)
 (0%)
Celkem 407 hlasů
 Komentářů: 34, poslední včera 12:54
Rozcestník

Jaký je váš názor na P versus NP?

P = NP
75% (2833)
P ≠ NP
11% (432)
Cože?
14% (521)

Celkem 3786 hlasů
Vytvořeno: 2.7.2013 12:45

Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

Komentáře

Vložit další komentář

2.7.2013 18:15 njn
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
hlasovani jako v parlamentu. takze se konecne dozvime, jak si to vlastne uzakonime? :-D
2.7.2013 20:23 pacholik | skóre: 10
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
kdepak, parlament není církev... zatím
3.7.2013 01:35 Kvakor
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
V USA se kdysi o něco podobného pokusili (naštestí neúspěšně) :-)
16.7.2013 15:21 Ferdinand
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
No co, v Indianě asi neměli rovný papír.
3.7.2013 09:22 pppcsr
Rozbalit Rozbalit vše A k čemu to je?

P ≠ NP, pokud řešení teprve hledám a

P = NP, jsou ty záblesky pravdy

Heuréka! :D ...

... Nefunguje to :(

3.7.2013 13:05 graviton
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
P=NP vede? Lidi nevěří na šifrování?
3.7.2013 13:50 Jan Grmela | skóre: 45 | blog: Kilo šťávy z lachtana | Brno
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Lidi neví, že P a NP souvisí s šifrováním :-)
Píšu pro Pivní recenze a protože mě to IT už fakt nebaví, tak jsme si s klukama postavili pivovar Lucky Bastard
5.7.2013 08:07 Vladimír Čunát | skóre: 19
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
+1 Zajímalo by mě jestli hlasující měli alespoň základní rozumnou představu o tom co ty třídy představují (ať už hlasovali pro rovnost nebo nerovnost).
5.7.2013 11:53 Michal Kubeček | skóre: 71 | Luštěnice
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Pokud někdo hlasuje pro jinou než třetí variantu, aniž by věděl nebo se podíval, co první dvě znamenají, tak je to jeho problém. Na druhou stranu, autor ankety IMHO měl přihodit odkaz na nějaký vysvětlující článek, protože i ten, kdo ví, o jakou otázku se jedná, si může potřebovat ověřit, která varianta je která.
8.8.2013 00:21 fny
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Pozor, chystáte se komentovat 36 dní dní starou diskusi. No a? Dnes vrácen lístek do Kauflandu po 43ech dnech od vrácení lahví. A taky z toho nedělám vědu.
11.8.2013 10:46 manasekp | skóre: 29 | blog: manasekp | Brno
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
to je aby se neporusilo casoprostorove kontinuum. Mohlo by te to potom vyplivnout v jinem vesmiru kde by te treba sezral savlozuby tygr.
BIOKOMP | Cas od casu se pokousim nekoho srazit k zemi abych se tam nevalel sam.
21.7.2013 17:27 Mira
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
třídy úloh znám, ale myslim si že použít rovnítko je špatně. když už tak použít znak podmnožiny či implikace
pavlix avatar 21.7.2013 21:40 pavlix | skóre: 54 | blog: pavlix
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Co je na rovnosti [množin] špatného?
Já už tu vlastně ani nejsem. Abclinuxu umřelo.
4.7.2013 09:47 Mti. | skóre: 31 | blog: Mti
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Veri, asi jako na potopy a dane. Je to neprijemne, je to tu a nic s tim neudelame.... je jim to jedno. :-)
Vidim harddisk mrzuty, jehoz hlava plotny se dotyka...
4.7.2013 20:52 JS
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Hlasoval jsem P/=NP, ale radeji bych si pral P=NP. Pokud by platilo P=NP, znamenalo by to tak vyrazny technicky pokrok, ze se proti tomu nefunkcnost sifrovani jevi jako dost mala cena.
stativ avatar 7.7.2013 16:49 stativ | skóre: 54 | blog: SlaNé roury
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
+1. P=NP by bylo super, ale vzhledem k tomu, že to za tak dlouhou dobu nebyl rovnost nikdo schopný dokázat ukazuje spíš na opak.
Ať sežeru elfa i s chlupama!!! ljirkovsky.wordpress.com stativ.tk
8.7.2013 10:51 Mti. | skóre: 31 | blog: Mti
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
To, ze to _jeste_ nekdo neudelal, neni dukaz toho, ze to nejde. :-D (cimz samozrejme netvrdim, ze tam ta rovnost je)
Vidim harddisk mrzuty, jehoz hlava plotny se dotyka...
pavlix avatar 8.7.2013 11:46 pavlix | skóre: 54 | blog: pavlix
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Rozlišuj dokazuje a ukazuje spíše na.
Já už tu vlastně ani nejsem. Abclinuxu umřelo.
8.7.2013 23:24 Mti. | skóre: 31 | blog: Mti
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Jiste. To se taky nehadam. :-)
Vidim harddisk mrzuty, jehoz hlava plotny se dotyka...
28.7.2013 13:36 Erbureth | skóre: 21
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
On taky ale nikdo nebyl schopen dokázat ani opak, takže to nic nedokazuje.
29.7.2013 12:46 Ondrej 'SanTiago' Zajicek
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Viz pavlixuv post vyse:
Rozlišuj dokazuje a ukazuje spíše na.
stativ avatar 31.7.2013 18:05 stativ | skóre: 54 | blog: SlaNé roury
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Tak tak. Bohužel číst předtím než na něco odpovím se zřejmě už moc nenosí.
Ať sežeru elfa i s chlupama!!! ljirkovsky.wordpress.com stativ.tk
6.7.2013 21:06 s
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Toto je velmi rozsirena fama. I kdyby se p=np nemusi to mit na sifrovani zadnej vliv. O(n^1000000) je porat dost zlozite a O(1.000001^n) je stale dost "neslozite" na to aby jsme mohli tvrdit, ze p=np nejak ovlivni soucasne sifrovani.
6.8.2013 11:45 extremni lama | skóre: 14 | blog: e_lama
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
one time pad by byl porad funkcni, tak jakypak "neveri na sifrovani"? :-)
The enemy of my enemy is still my enemy.
egg avatar 8.8.2013 00:53 egg | skóre: 20 | Praha
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
P=NP vede? Lidi nevěří na šifrování?
On už někdo dokázal, že faktorizace je NPC?
8.8.2013 02:22 Ondrej 'SanTiago' Zajicek
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Irelevantni. Pokud P=NP, tak sifrovani postavene na obtiznosti faktorizace je rozlousknutelne v polynomialnim case bez ohledu na to, zda faktorizace je NP-kompletni nebo neni (staci ze je v NP, a to je zrejme).
egg avatar 8.8.2013 10:35 egg | skóre: 20 | Praha
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Pokud P=NP, tak sifrovani postavene na obtiznosti faktorizace je rozlousknutelne v polynomialnim case ...
Zrovna tak je ale možné, že P≠NP, přičemž faktorizace je v P. Čili tak nebo tak, obvyklé šifrování je založeno na víře bez důkazu. :-)
24.8.2013 16:23 ...
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
chytrych lidi uz se narodilo za tu dobu dost, aby to nekdo uz rozlousknul. jen si to nechal pro sebe a par znamych, jak ze se to veci maji.
24.8.2013 19:06 potato
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Pitomost. Naprostá většina matermatických problémů je těžká ve smyslu poměru komplexnosti nejjednoduššího důkazu vůči komplexnosti formulace problému. Myslet si, že když existuje je spousta chytrých lidí, že musejí být schopni ty problémy vyřešit, je asi jako si myslet, že většina reálných čísel je racionální...
Dreit avatar 3.7.2013 17:59 Dreit | skóre: 15 | blog: Dreit a jeho dračí postřehy | Královehradecký kraj
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?

P+NP, to bude tranzistor :-D

Nope
4.7.2013 11:12 SiO2
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Tahle diskuse je celá nějaká zFETovaná.
12.7.2013 15:35 mluno
Rozbalit Rozbalit vše Re: Jaký je váš názor na PNP versus NPN?
Taky jsem myslel na tranzistory, proto jsem se dostal sem, doufaje, že to tu někdo nám tápajícím (možnost "cože?") trochu osvětlí. Ale je vidět, že skoro nikdo (včetně mě) neví, vo co gou.
stativ avatar 12.7.2013 17:19 stativ | skóre: 54 | blog: SlaNé roury
Rozbalit Rozbalit vše Re: Jaký je váš názor na PNP versus NPN?
Pro tápající: P je skupina problémů, pro které existuje algoritmus s polynomiální složitostí. NP jsou polynomiálně verifikovatelné problémy, tj. problémy, kde se neví, jestli existuje algoritmus s polynomiální složitostí (kdyby ano, pak by bylo P=NP), ale existuje polynomiální algoritmus pro ověření řešení* (tzn. když si nějaké řešení vycucám z prstu, můžu v polynomiálním čase ověřit, jestli to je platné řešení).

V praxi jde o to, že polynomiální algoritmy jsou obvykle rozumně rychlé (samozřejmě polynomiální algoritmus řádu deset milionů je stejně nahouby jako brute force u NP), kdežto u NP jsou algoritmy nějakým způsobem založeny na bruteforce (tj. vycucávám si z prstu řešení a ty pak polynomiálně ověřuji) a tedy kurevsky pomalé.
* existují ale i horší problémy než NP, kde není znám ani algoritmus pro ověření.
Ať sežeru elfa i s chlupama!!! ljirkovsky.wordpress.com stativ.tk
3.7.2013 19:38 Jiří
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Nemůžu uvěřit, že možnost "Cože?" má víc jak 0.
Dreit avatar 3.7.2013 21:10 Dreit | skóre: 15 | blog: Dreit a jeho dračí postřehy | Královehradecký kraj
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?

Nemůžu uvěřit, že tomu někdo nemůže uvěřit.

Nope
4.7.2013 08:17 w4rr10r
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Nemůžu uvěřit, že nemůžeš uvěřit tomu, že tomu někdo nemůže uvěřit.
pavlix avatar 8.7.2013 11:51 pavlix | skóre: 54 | blog: pavlix
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Volil jsem cože, protože mi to přijde jako nejpřirozenější reakce na to, že se takováto otázka objeví (zde) v anketě.
Já už tu vlastně ani nejsem. Abclinuxu umřelo.
4.7.2013 12:16 manasekp | skóre: 29 | blog: manasekp | Brno
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Coze? :-D
BIOKOMP | Cas od casu se pokousim nekoho srazit k zemi abych se tam nevalel sam.
4.7.2013 14:12 R
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Vacsina IT ludi a dokonca aj vacsina programatorov to nikdy nebude potrebovat.
5.7.2013 20:51 aubi
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
hm, zrovna se v tom jeden kamarad koupe

Bohuzel, ten samy pristup ma spousta lidi ke slozitosti algoritmu. To je blbost, to nepotrebuju! Uzivatel se pak muze vzteknout a ti, co tomu rozumi, muzou vylozene vyletet z kuze.
4.7.2013 17:21 Petr Šobáň | skóre: 79 | blog: soban | Olomouc
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
A proč ? Já jsem dal taky cože protože nevím co je myšleno tím P a co tím NP......
19.7.2013 09:23 potato
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Volil jsem cože, i když vím, co je P a NP, protože to je jediné, co se na takovou otázku v anketě dá napsat. Navíc většina zajímavých možností tu dichotomii stejně nějak rozbíjí...
Fluttershy, yay! avatar 4.7.2013 08:18 Fluttershy, yay! | skóre: 83 | blog:
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
P = NP iff N je neutrální prvek vzhledem k použité operaci (násobení?).
4.7.2013 08:42 Michal Kubeček | skóre: 71 | Luštěnice
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Špatně.
Fluttershy, yay! avatar 4.7.2013 21:18 Fluttershy, yay! | skóre: 83 | blog:
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Rád se nechám poučit.
4.7.2013 23:33 Ondrej 'SanTiago' Zajicek
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
'NP' je zde chapano jako jeden symbol, nikoliv jako term slozeny z binarniho operatoru a dvou symbolu 'N' a 'P'.
Fluttershy, yay! avatar 5.7.2013 00:05 Fluttershy, yay! | skóre: 83 | blog:
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Ach, ty předpoklady. Na námitku duck test reaguji judging a book by its cover.
5.7.2013 00:13 Michal Kubeček | skóre: 71 | Luštěnice
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Stačí aby P bylo nulové, pak to platí pro libovolné N. Pokud existují netriviální rozklady nuly na součin, není potřeba ani to, např. v ℤ/6ℤ je řešením i třeba P=2, N=4.
5.7.2013 12:22 Ondrej 'SanTiago' Zajicek
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Ono zavisi na tom, zda 'N' a 'P' interpretujeme jako symboly promennych nebo konstant. Pokud 'N' chapu jako konstantu a 'P' jako promennou (a 'iff' jako metalogickou ekvivalenci), tak je puvodni post spravne.

I kdyz da se opravnene namitnout, ze pokud to neni zrejme z kontextu, tak by pro prehlednost mely byt vsechny promenne okvantifikovane, ale algebraici na tohle kaslou.
5.7.2013 12:43 VD
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Ještě ne, musíte si také domyslet, že použitá operace je komutativní. Kdyby použitá operace byla vrať druhý operand, tak levá část platí, ale neutrální prvek neexistuje. Ale to si autor sám naběhl, že se zamotal do neutrálního prvku k operaci, a nenapsal prostě N = 1.
5.7.2013 12:52 Ondrej 'SanTiago' Zajicek
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Jo, a nebo do puvodniho tvrzeni misto 'neutralniho prvku' dosadit 'leve neutralni prvek'.
5.7.2013 13:03 Michal Kubeček | skóre: 71 | Luštěnice
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Když se implicitně předpokládá velký kvantifikátor, tak je zvykem ho vztahovat na celé tvrzení, ne na nějakou jeho náhodně vybranou část.
8.7.2013 12:48 Ondrej 'SanTiago' Zajicek
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Ono to je v tomto pripade jedno - to tvrzeni plati i kdybych je cele interpretoval jako jednu logickou formuli, 'iff' jako logickou spojku, 'N' i 'P' jako promenne a druhou cast (za 'iff) jako jeden unarni predikat I(N). Protoze plati (forall x)(forall y)(F(x,y) <-> G(x)) <-> (forall x)( (forall y)F(x, y) <-> G(x)) (kdyz y neni volna v G(x)).
8.7.2013 13:10 Michal Kubeček | skóre: 71 | Luštěnice
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Jenže tohle není ten případ, tady by to muselo být "(∀P: NP = P) ⇔ (N je neutrální prvek)", aby to dávalo smysl. A pak by to tvrzení bylo v podstatě k ničemu, protože by to vlastně byla definice.
8.7.2013 20:14 Ondrej 'SanTiago' Zajicek
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Vsak si do te ekvivalence, kterou zminuju vyse, dosad: formule F(x,y) je xy=y, formule G(x) je unarni relace 'x je (leve) neutralni prvek k prislusne operaci', prava strana je defacto definice leve neutralniho prvku, leva strana je to, co je v puvodnim postu. Takze z definice neutr. prvku a z platnosti te ekvivalence vyse je platny i puvodni post.
8.7.2013 22:35 Michal Kubeček | skóre: 71 | Luštěnice
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?

Teď jsem si tu změť závorek prohlédl pořádně a vypadá to, že celý optický trik spočívá v tom, co přesně myslíte nejednoznačným zápisem "(forall y)F(x, y) <-> G(x)". Pokud to znamená "∀y: [F(x,y) ⇔ G(x)]", pak je sice vaše (hlavní) ekvivalence pravdivá, ale pro výše uvedený příklad jsou obě strany nepravdivé. Pokud to znamená "[∀y: F(x,y)] ⇔ G(x)", pak to pravda není a výše máte protipříklad.

Takže ještě jednou, co jsem chtěl říct: pokud napíšu "V(p,q)" bez jakékoli kvantifikace, tak se tím obvykle myslí "∀p,q: V(p,q)", ne že k nějakým podvýrazům začnu náhodně připisovat kvantifikátory tak, aby to vyšlo. Koneckonců i reakce autora toho původního příspěvku naznačuje, že i on to tak myslel.

pavlix avatar 8.7.2013 23:03 pavlix | skóre: 54 | blog: pavlix
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Takže ještě jednou, co jsem chtěl říct: pokud napíšu "V(p,q)" bez jakékoli kvantifikace, tak se tím obvykle myslí "∀p,q: V(p,q)"
Něco takového matfyzáci učili na predikátové logice jako pravidlo generalizace.
Já už tu vlastně ani nejsem. Abclinuxu umřelo.
Fluttershy, yay! avatar 8.7.2013 23:14 Fluttershy, yay! | skóre: 83 | blog:
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Závisí ještě na volných proměnných.
pavlix avatar 8.7.2013 23:16 pavlix | skóre: 54 | blog: pavlix
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
?
Já už tu vlastně ani nejsem. Abclinuxu umřelo.
Fluttershy, yay! avatar 8.7.2013 23:19 Fluttershy, yay! | skóre: 83 | blog:
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
No to by mě taky zajímalo. Obávám se, že jsem si spletl okno.
9.7.2013 01:08 Ondrej 'SanTiago' Zajicek
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Něco takového matfyzáci učili na predikátové logice jako pravidlo generalizace.

Ono to v prve rade vychazi uz ze semantiky formuli s volnymi promennymi. Pravidlo generalizace je pak jen syntakticke pravidlo, ktere zajistuje, aby k semanticke 'ekviplatnosti' byla i syntakticka 'ekvidokazatelnost'.
9.7.2013 01:00 Ondrej 'SanTiago' Zajicek
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
V textech o logice se bezne pouziva konvence, ze kvantifikatory 'vazou tesneji' nez logicke spojky, takze to znamena "[∀y: F(x,y)] ⇔ G(x)". Ale je pravda, ze v mem postu #39 jsem se hloupe spletl a ta mnou zminovana ekvivalence neplati, takze me dva prichozi prispevky jsou nesmysly. Kazdopadne muj post #25 tim neni postizen.
akže ještě jednou, co jsem chtěl říct: pokud napíšu "V(p,q)" bez jakékoli kvantifikace, tak se tím obvykle myslí "∀p,q: V(p,q)", ne že k nějakým podvýrazům začnu náhodně připisovat kvantifikátory tak, aby to vyšlo
To je pravda, ale je treba si uvedomit dve veci:

Zaprve, protoze se 'implicitne okvantifikuje' cela logicka formule, je treba vedet, kde konci logicke formule a kde uz jsou metalogicke konstrukce. Napr. formule "F(x) <-> G(x)" bude ekvivalentni "(forall x)(F(X) <-> G(x))", zatimco tvrzeni "F(x) je pravdive iff G(x) je pravdive" (kde F(x) a G(x) jsou formule, zbytek jsou metalogicke konstrukce) bude ekvivalentni "(forall x)F(x) je pravdive iff (forall x)G(x) je pravdive" .

Zadruhe, je treba rozlisit symboly promennych a symboly konstant - k 'implicitnimu okvantifikovani' dojde pouze u promennych (ty maji vzdy platnost nejvyse v ramci jedne formule), zatimco konstanty si zachovavaji stejny vyznam v cele sade formuli. Co je promenna a co je konstanta je dano pouzitym jazykem (tedy defacto konvenci) a muze se lisit aplikace od aplikace. Pokud tedy interpretuji nezavisly post, zbyva akorat hadat z kontextu.

To, ze druha cast puvodniho Davkolova postu (za 'iff' vcetne) je psana plaintextem a navic vyuziva konstrukce primo nepopsatelne v logice prvniho radu (odkazuje se na pouzitou operaci), svadi k interpretaci, ze formule je pouze "P=NP" a zbytek je matematicky kontext. Protoze 'N' se vyskytuje jak ve formuli tak v kontextu, tak nemuze jit o promennou (to by nedavalo smysl), ale o konstantu. Z toho vysla argumentace v postu #25.
Fluttershy, yay! avatar 6.7.2013 01:25 Fluttershy, yay! | skóre: 83 | blog:
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
OK, poučení pro příště: nepsat komentáře příliš brzy ráno.
5.7.2013 12:47 Ondrej 'SanTiago' Zajicek
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
FYI: tady je clanek rozebirajici podobny pruzkum mezi prevazne compsci akademiky, tam vetsina hlasovala pro P != NP.

Par zajimavych (hypotetickych) moznosti:

- P = NP bude ukazano jako nezavisle vuci beznym axiomatizacim aritmetiky (tedy v nich nejde dokazat ani P = NP, ani P != NP).

- P = NP bude dokazano pomoci ciste nekonstruktivniho dukazu.

- P = NP, ale dolni odhad pro polynomialni algoritmus bude tak obrovsky, ze pro vsechna rozumna cisla bude stejne rychlejsi exponencialni algoritmus.
mirefek avatar 19.7.2013 12:09 mirefek | skóre: 6 | blog: proc_dalsi_nazev
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Možnost 3 pominu, je teoreticky nejzajímavá. Je třeba podotknout, že existuje algoritmus, který (a je to o něm dokázané) běží v polynomiálním čase právě tehdy když P=NP. To znamená, že ryze "nekonstruktivní" tvrzení P=NP být nemůže -- tedy možnost 2 je možné v podstatě vyloučit. Možnost 1 pak bude znamenat, že bude existovat algoritmus, který poběží v polynomiálním čase, ale nebude to o něm možné dokázat.

Jak pracuje onen polynomiální algoritmus? Očísluje si všechny možné algoritmy Alg_0, Alg_1, Alg_2,... Pak spustí Alg_0 s maximálním časem 1, pokud do té doby Alg_0 vrátí nějakou odpověď ověříme, zda je to řešení našeho problému. Pak spustí postupně Alg_0 a Alg_1 s maximálním časem 2 a ověří jejich odpovědi. Pak spustí postupně Alg_0, Alg_1, Alg_3 s maximálním časem 3 a ověří jejich odpovědi. Atd. Pokud existuje správný polynomiální algoritmus Alg_k, náš algoritmus se k němu dostane v konstantním čase (vzhledem k velikosti vstupu) a v polynomiálním čase tak získá řešení.
mirefek avatar 19.7.2013 12:11 mirefek | skóre: 6 | blog: proc_dalsi_nazev
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Pardon kecám, možnost 1 znamená, že bude existovat algoritmus, o kterém nebude možné určit, zda v polynomiálním čase běží nebo ne, ale určitě nebude existovat algoritmus, o kterém to půjde dokázat.
20.7.2013 14:35 Ondrej 'SanTiago' Zajicek
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Očísluje si všechny možné algoritmy Alg_0, Alg_1, Alg_2 ...
Tohle vypada jak standardni Levinuv prohledavaci algoritmus, ten ma ale jednu teoretickou vadu - protoze je schopen validovat jen pozitivni reseni (pokud nemame konstruktivne NP=co-NP nebo horni odhad na polynom u polynomialniho algorimu pro dany NP-uplny problem), tak se zacykli v pripade, kdy odpoved ma byt negativni. Coz tedy znamena, ze nesplnuje definici polynomialnich rozhodovacich algoritmu (kde se pozaduje zastaveni vzdy) vymezujicich tridu P.

Ale mozna to je nejaky vylepseny argument ktery neznam, pak bych prosil o detaily.

I kdybychom ale meli takto vylepseny algoritmus, tak to striktne vzato nevylucuje, ze by samotne tvrzeni 'P=NP' bylo dokazano ciste nekonstruktivnimi metodami. On takovy univerzalni algoritmus totiz neprinasi moc vhledu do te problematiky, coz by snad explicitni konstrukce mohla.
že bude existovat algoritmus, o kterém nebude možné určit, zda v polynomiálním čase běží nebo ne, ale určitě nebude existovat algoritmus, o kterém to půjde dokázat.
Tady mi neni jasne, co presne tou vetou myslis. Moznost 1 znamena, ze plati jedna z techto trech moznosti:

1a. v N plati P=NP, tedy vhodny algoritmus existuje, ale prokazatelne to o nem nejde dokazat (v pouzitem formalismu)

1b. v N neplati P=NP, ale ani tohle prokazatelne nelze dokazat

1c. nejaky novy prevratny pohled na logiku, aritmetiku a prirozena cisla.

AFAIK ani jednu z techto trech moznosti nemuzu vyloucit, ale rad se necham poucit.
mirefek avatar 20.7.2013 16:17 mirefek | skóre: 6 | blog: proc_dalsi_nazev
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Ajta, asi jsem se vyjadril k necemu, do ceho zas tak podrobne nevidim. Mym cilem bylo si rozmyslet, co vlastne ty hypoteticke logicke varianty znamenaji. Napriklad pro hypotezu prvociselnych dvojic by byl nesmysl dokazovat nezavislost (jakkoli muze napr. v TeMnu platit).
Tohle vypada jak standardni Levinuv prohledavaci algoritmus, ten ma ale jednu teoretickou vadu - protoze je schopen validovat jen pozitivni reseni.

Ale mozna to je nejaky vylepseny argument ktery neznam, pak bych prosil o detaily.
Je to jen Levinuv algoritmus. Slysel jsem to kdysi od jednoho cloveka a neuvedomil jsem si tenhle zadrhel. Kdyz tak se ho zeptam, jestli k tomu vi neco vic.
On takovy univerzalni algoritmus totiz neprinasi moc vhledu do te problematiky, coz by snad explicitni konstrukce mohla.
S tim souhlasim.
1a. v N plati P=NP, tedy vhodny algoritmus existuje, ale prokazatelne to o nem nejde dokazat (v pouzitem formalismu)

1b. v N neplati P=NP, ale ani tohle prokazatelne nelze dokazat
Tak nejak jsem si to predstavoval :-). A jeste tedy (jestli ten Levinuv algoritmus nejde vylepsit) muzem k 2. dodat, ze by i v onom pripade mohlo platit 1a., zatimco v 1. by prokazatelne ani neslo dokazat, ze nastala moznost 1a.
29.7.2013 08:20 walkeer_CZ
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
technicky dotaz laika: kde berete jistou, ze algoritmy jsou spocitatelne, tedy ze jdou seradit?
29.7.2013 12:45 Ondrej 'SanTiago' Zajicek
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
To trivialne splnuji vsechny (vzajemne vicemene ekvivalentni) definice algoritmu.
31.7.2013 20:31 potato
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Zjednodušeně řečeno, každý algoritmus můžeš zapsat konečným řetězcem tvořeným symboly z konečné množiny. Třeba jako program v COBOLu... Z toto je očíslovatelnost přirozenými čísly zjevná.
1.8.2013 07:02 petr_p | skóre: 59 | blog: pb
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Algoritmus ale není program. Je otazné, zda-li ke každému algoritmu existuje program. Například algoritmus popisující práci nedeterministického automatu operuje s orákulem, které umí rozhodnout, zda-li existuje řešení. Implementaci tohoto algoritmu – tedy program – jsem ještě neviděl. Asi to závisí na definici algoritmu.
1.8.2013 14:53 Ondrej 'SanTiago' Zajicek
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Algoritmus ale není program.

Rozdil mezi algoritmem a programem neni moc relevantni. Vsechny pouzivane formalizace pojmu 'algoritmus' jsou ve vysledku ekvivalentni beznym programum (viz Church-Turing thesis).
Například algoritmus popisující práci nedeterministického automatu operuje s orákulem, které umí rozhodnout, zda-li existuje řešení. Implementaci tohoto algoritmu – tedy program – jsem ještě neviděl.
Tady ale neni rozdil v tom, ze jedno by bylo algoritmus a druhy program, ale to, ze v prvnim pripade implicitne predpokladas jiny vypocetni model nez v druhem. Pokud tvuj vypocetni model predpoklada moznost dotazu nejakeho typu orakula, tak ten dotaz muzes pouzit jak v (neformalnim) algoritmu, tak ve (formalne definovanem) programu. Pokud ne, tak ho nemuzes pouzit ani v jednom.
2.8.2013 03:11 Kvakor
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Ano, například pokud by se jako orákulum použila časová smyčka z budoucnosti, tak je možné napsat jak algoritmust, tak program, protože onen (zdánlivý) nedeterminismus je realizovaný specializovaným hadwarem (který může být něco velmi exotického, jako třeba červí minidíra plus příslušenství) a samotnou podstatou času, resp. tím, že časové paradoxy nemohou nastat. Z pohledu programu to prostě bude obyčejné vstupně-výstupní zařízení, ze kterého je možné číst data ještě před tím, než je tam zapíšete.

Mimochodem, pokud by to opravdu šlo, tak by to znamenalo částečně P==NP, tedy alespoň u problémů, kde je snadné ověřit řešení v čase danném časovou smyčkou.
2.8.2013 10:26 Ondrej 'SanTiago' Zajicek
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Mimochodem, pokud by to opravdu šlo, tak by to znamenalo částečně P==NP,
Neznamenalo, protoze tridy P, NP jsou definovane pro konkretni vypocetni model (turinguv stroj bez takove periferie a modely ekvivalentni vypocetni sily). Existuji relativizovane definice, ale ty se znaci trochu jinak (napr P(X) pro turiguv stroj s orakulem pro mnozinu X). Takze spis by to znamenalo P' >= NP, kde P' je trida uloh polynomielne resitelnych na turingove stroji s tou casovou smyckou.
Josef Kufner avatar 21.8.2013 02:14 Josef Kufner | skóre: 68
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
To sice jo, ale dostaneš nástroj, který umí řešit NP-úplný problém v konstantním čase.
Hello world ! Segmentation fault (core dumped)
5.7.2013 19:02 Jirka | skóre: 24
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Pal-NePal? :-)
Dokud to funguje, nešťourej se v tom!... Jak opravit vadnou SD kartu
Dreit avatar 6.7.2013 23:35 Dreit | skóre: 15 | blog: Dreit a jeho dračí postřehy | Královehradecký kraj
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?

SECAM

Nope
8.7.2013 19:55 ramwi
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Myslim, ze nekdy v roce 2010 Vinay Deolalikar prohlasil, ze disponuje dukazem, ze P!=NP, nasledoval rok dohadu a zkoumani dane myslenky, ktery ale bohuzel nevedl k nicemu rozumnemu a nasledne se cela problematika zanorila nekam pod obzor me pozornosti. Netusite nekdo, jak to nakonec dopadlo? (i kdyz i to je asi domyslitelne z toho, ze uz se o tom nijak prilisne nemluvi) Stranka pane Deolalikara ovsem tvrdi (uz asi rok), ze se ceka jen na schvaleni revieweru a dukaz muze do tisku.
13.7.2013 22:16 Vladimír Čunát | skóre: 19
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Žádný ani vzdáleně přijatelný důkaz zatím není veřejně známý (pro rovnost ani nerovnost; jsem teoretický informatik).
9.7.2013 23:40 B.E.
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
zvolil jsem "C" a (po přečtení všech příspěvků) jsem na to hrdej! :o)
16.7.2013 12:01 osolemio
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Píchač/NePíchač ... ?
Petr Maleček avatar 19.7.2013 23:52 Petr Maleček | skóre: 27 | Plzeň - Bolevec
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Já od začátku preferuji PnP.
LinMuck, WinFuck :-P - pokud by mi někdo chtěl pomoct s prostorem na DropBoxu a sám získat 250MB, tak zde.
21.7.2013 01:27 manasekp | skóre: 29 | blog: manasekp | Brno
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Plug and pray? :-D
BIOKOMP | Cas od casu se pokousim nekoho srazit k zemi abych se tam nevalel sam.
22.7.2013 01:35 kaja47 | blog: k47
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
Další možnosti jsou, že se nikdy nepodaří dokázat rovnost ani nerovnost a pak, že P = NP, ale polynomiální algoritmy mají tak astronomické konstantní faktory, že na rovnosti nakonec nesejde.
26.7.2013 12:38 alenka
Rozbalit Rozbalit vše Re: Jaký je váš názor na P versus NP?
obecně se to nerovná, ale pro P=0 nebo N=1 pochopitelně ano

Založit nové vláknoNahoru

ISSN 1214-1267   www.czech-server.cz
© 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.