Polské vývojářské studio CD Projekt Red publikovalo na Printables.com 3D modely z počítačové hry Cyberpunk 2077.
Organizátoři konference LinuxDays 2025 vydali program a zároveň otevřeli registrace. Akce se uskuteční 4. a 5. října na FIT ČVUT v pražských Dejvicích, kde vás čekají přednášky, workshopy, stánky a spousta šikovných lidí. Vstup na akci je zdarma.
Uživatelé komunikátoru Signal si mohou svá data přímo v Signalu bezpečně zálohovat a v případě rozbití nebo ztráty telefonu následně na novém telefonu obnovit. Zálohování posledních 45 dnů je zdarma. Nad 45 dnů je zpoplatněno částkou 1,99 dolaru měsíčně.
Server Groklaw, zaměřený na kauzy jako právní spory SCO týkající se Linuxu, skončil před 12 lety, resp. doména stále existuje, ale web obsahuje spam propagující hazardní hry. LWN.net proto v úvodníku připomíná důležitost zachovávání komunitních zdrojů a upozorňuje, že Internet Archive je také jen jeden.
Jakub Vrána vydal Adminer ve verzi 5.4.0: "Delší dobu se v Admineru neobjevila žádná závažná chyba, tak jsem nemusel vydávat novou verzi, až počet změn hodně nabobtnal."
V Německu slavnostně uvedli do provozu (en) nejrychlejší počítač v Evropě. Superpočítač Jupiter se nachází ve výzkumném ústavu v Jülichu na západě země, podle německého kancléře Friedricha Merze otevírá nové možnosti pro trénování modelů umělé inteligence (AI) i pro vědecké simulace. Superpočítač Jupiter je nejrychlejší v Evropě a čtvrtý nejrychlejší na světě (TOP500). „Chceme, aby se z Německa stal národ umělé inteligence,“ uvedl na
… více »V Berlíně probíhá konference vývojářů a uživatelů desktopového prostředí KDE Plasma Akademy 2025. Při té příležitosti byla oznámena alfa verze nové linuxové distribuce KDE Linux.
Byl vydán Debian 13.1, tj. první opravná verze Debianu 13 s kódovým názvem Trixie a Debian 12.12, tj. dvanáctá opravná verze Debianu 12 s kódovým názvem Bookworm. Řešeny jsou především bezpečnostní problémy, ale také několik vážných chyb. Instalační média Debianu 13 a Debianu 12 lze samozřejmě nadále k instalaci používat. Po instalaci stačí systém aktualizovat.
Evropská komise potrestala Google ze skupiny Alphabet pokutou 2,95 miliardy eur (71,9 miliardy Kč) za porušení antimonopolní legislativy. Podle EK, která mimo jiné plní funkci antimonopolního orgánu EU, se Google dopustil protisoutěžních praktik ve svém reklamním byznysu. Google v reakci uvedl, že rozhodnutí považuje za chybné a hodlá se proti němu odvolat. EK ve věci rozhodovala na základě stížnosti Evropské rady vydavatelů. Podle
… více »Podpora 32bitového Firefoxu pro Linux skončí v roce 2026. Poslední podporované 32bitové verze budou Firefox 144 a Firefox 140 s rozšířenou podporou, jehož podpora skončí v září 2026.
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:
P ≠ NP, pokud řešení teprve hledám a
P = NP, jsou ty záblesky pravdy
Heuréka! :D ...
... Nefunguje to :(
Rozlišuj dokazuje a ukazuje spíše na.
P=NP vede? Lidi nevěří na šifrování?On už někdo dokázal, že faktorizace je NPC?
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.
P+NP, to bude tranzistor
Nemůžu uvěřit, že tomu někdo nemůže uvěřit.
(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)).
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.
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.
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'.
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šloTo 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.
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.
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 dokazatTak nejak jsem si to predstavoval
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.
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.
SECAM