Complexity and Infinity

Jan 23, 2014

Sprecher:innen

Über

When the set theory was axiomatized, the guiding principle was to keep as many properties of finite sets as possible also for infinite sets. Today, lacking methods to solve problems in complexity theory, we are, in a sense, doing the opposite: we make conjectures about finite structures using facts that are true about similar infinite structures. For example, our belief that P ≠ NP is mainly supported by the fact that recursively enumerable sets are not recursive. I will give some examples of such conjectures in complexity theory and mention some results that can be viewed as corroboration of their validity. These examples come from proof complexity – a field that studies complexity from the perspective of logic – but these conjectures can also be stated in purely computational terms. One of the conjectures is that there is no complete problem for a certain class of search problems.

Organisator

Kategorien

Über Pražský informatický seminář

Seminář se bude scházet vždy 4. čtvrtek v měsíci v 16 hod. (s výjimkou letních měsíců a prosince), a to buď v budově FEL ČVUT na Karlově náměstí, nebo v budově MFF UK na Malostranském náměstí. Jeho program bude tvořen hodinovou přednáškou, po níž bude následovat časově neomezená diskuse. Základem přednášky by mělo být něco (v mezinárodním měřítku) mimořádného nebo aspoň pozoruhodného, na co přednášející přišel a co vysvětlí způsobem srozumitelným a zajímavým i pro širší informatickou obec. Přednášky budou standardně v angličtině. Formát semináře připravil přípravný výbor ve složení Roman Barták (MFF UK), Michal Chytil (ÚI AVČR), Pavel Kordík (FIT ČVUT), Jan Kybic (FEL ČVUT), Michal Pěchouček (FEL ČVUT), Jiří Sgall (MFF UK), Vojtěch Svátek (FIS VŠE), Michal Šorel (ÚTIA AV ČR), Tomáš Werner (FEL ČVUT), Filip Železný (FEL ČVUT) Idea Pražského informatického semináře vznikla z rozhovorů představitelů několika vědeckých institucí na téma, jak odstranit zbytečnou fragmentaci informatické komunity v ČR.

Präsentation speichern

Soll diese Präsentation für 1000 Jahre gespeichert werden?

Wie speichern wir Präsentationen?

Ewigspeicher-Fortschrittswert: 0 = 0.0%

Freigeben

Empfohlene Videos

Präsentationen, deren Thema, Kategorie oder Sprecher:in ähnlich sind

Interessiert an Vorträgen wie diesem? Pražský informatický seminář folgen