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 14:44 | Komunita

Mozilla.cz informuje, že Firefox bude možná upozorňovat na úniky vašich hesel. V Mozille prototypují upozorňování na únik informací o vašem účtu, pokud se na seznamu Have I been pwned? objeví služba, ke které máte ve Firefoxu uložené přihlašovací údaje. Informace se objevila v pravidelném newsletteru o vývoji Firefoxu.

Ladislav Hagara | Komentářů: 5
včera 00:22 | Bezpečnostní upozornění

Společnost ZONER informuje o bezpečnostním incidentu, při kterém došlo ke zcizení a zveřejnění části přihlašovacích údajů zákazníků k elektronické poště a webhostingu CZECHIA.COM.

Ladislav Hagara | Komentářů: 0
22.11. 23:44 | Nová verze

Byla vydána nová stabilní verze 1.13 (1.13.1008.32) webového prohlížeče Vivaldi (Wikipedie). Z novinek vývojáři zdůrazňují možnost zobrazení otevřených i uzavřených listů pomocí ikonky Okno na postranní liště a vylepšené stahování (YouTube). Nejnovější Vivaldi je postaveno na Chromiu 62.0.3202.97.

Ladislav Hagara | Komentářů: 9
22.11. 20:55 | Nová verze

Byla vydána verze 2017.3 dnes již průběžně aktualizované linuxové distribuce navržené pro digitální forenzní analýzu a penetrační testování Kali Linux. Aktualizovat systém lze pomocí příkazů "apt update; apt dist-upgrade; reboot". Z novinek lze zmínit 4 nové nástroje: InSpy, CherryTree, Sublist3r a OSRFramework.

Ladislav Hagara | Komentářů: 1
22.11. 01:55 | Bezpečnostní upozornění

Společnost Uber potvrdila bezpečnostní incident a únik dat v roce 2016. Unikly údaje o 57 milionech cestujících (jména, emailové adresy a čísla mobilních telefonů) a 600 tisících řidičích (navíc čísla řidičských průkazů).

Ladislav Hagara | Komentářů: 1
21.11. 23:44 | Humor

Co vypíše příkaz man půl hodiny po půlnoci? Text "gimme gimme gimme". Jedná se o virtuální velikonoční vajíčko připomínající skupinu ABBA a její hit Gimme! Gimme! Gimme! (A Man After Midnight). Problém nastane, pokud gimme gimme gimme nabourá automatizované testování softwaru. To se pak příkaz man musí opravit [Bug 1515352] [reddit].

Ladislav Hagara | Komentářů: 10
21.11. 18:11 | Zajímavý článek

Mozilla.cz informuje, že Firefox na Fedoře podporuje Client Side Decorations. Firefox na Linuxu se vykresluje včetně standardního záhlaví okna, které je v případě webového prohlížeče většinou nadbytečné a ubírá drahocenné vertikální místo na obrazovce. Verze distribuovaná uživatelům Fedory však nyní obsahuje experimentální podporu pro takzvané Client Side Decorations, které umožňují vykreslování „oušek“ panelů do záhlaví okna.

Ladislav Hagara | Komentářů: 12
21.11. 05:00 | Bezpečnostní upozornění

Maxim Goryachy a Mark Ermolov ze společnosti Positive Technologies budou mít v prosinci na konferenci Black Hat Europe 2017 přednášku s názvem "Jak se nabourat do vypnutého počítače, a nebo jak v Intel Management Engine spustit vlastní nepodepsaný kód". O nalezeném bezpečnostním problému informovali společnost Intel. Ta bezpečnostní problém INTEL-SA-00086 v Intel Management Engine (ME), Intel Server Platform Services (SPS) a Intel

… více »
Ladislav Hagara | Komentářů: 47
21.11. 01:33 | Zajímavý projekt

Na Humble Bundle byla spuštěna akce Humble Book Bundle: Java. Za 1 dolar a více lze koupit 5 elektronických knih, za 8 dolarů a více 10 elektronických knih a za 15 dolarů a více 15 elektronických knih věnovaných programovacímu jazyku Java od nakladatelství O'Reilly. Peníze lze libovolně rozdělit mezi nakladatelství O'Reilly, neziskovou organizaci Code for America a Humble Bundle.

Ladislav Hagara | Komentářů: 0
21.11. 00:11 | Zajímavý projekt

Článek na OMG! Ubuntu! představuje rodinu písma IBM Plex. Jedná se o open source písmo (GitHub) navržené a uvolněné společností IBM (YouTube, Carbon Design System). Ukázka na Font Squirrel.

Ladislav Hagara | Komentářů: 14
Jak se vás potenciálně dotkne trend odstraňování analogového audio konektoru typu 3,5mm jack z „chytrých telefonů“?
 (9%)
 (1%)
 (1%)
 (1%)
 (75%)
 (14%)
Celkem 756 hlasů
 Komentářů: 37, poslední 21.11. 15:21
    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?
    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.
    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: 20
    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ě.
    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: 81 | 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: 81 | 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: 81 | 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.
    Fluttershy, yay! avatar 8.7.2013 23:14 Fluttershy, yay! | skóre: 81 | 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?
    ?
    Fluttershy, yay! avatar 8.7.2013 23:19 Fluttershy, yay! | skóre: 81 | 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: 81 | 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: 67
    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: 23
    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.