The Union of Czech Mathematicians and Physicists

Seminář pořádaný Odbornou skupinou České fyzikální společnosti JČMF Organizace výzkumu.

Abstract

A non-uniform computational model permits us to design, for every natural number n, a program P_n to be run solely on the 2^n bit strings of length n, where the size of the program P_n can itself grow with n. Such infinite computational models can be very powerful, even when the sizes and running times of P_n are bounded by a polynomial in n. Therefore a lower bound against non-uniform computation is among the strongest form of impossibility result that one can obtain in complexity theory. Correspondingly, such results are also among the most difficult to prove; the area of non-uniform computation contains many embarrassingly open questions. For example, it is still open to find a function computable in exponential time that cannot be computed with non-uniform families of programs of polynomial size and polynomial running time. (If no such function existed, then every exponential-time function could be simulated "efficiently" - provided that one is allowed unbounded time to design a separate but short program for each input length.)

Letní škola chemie, fyziky, biologie a matematiky je tradiční prázdninová akce Přírodovědecké fakulty Univerzity Palackého, která se každoročně koná v prostorách Gymnázia a Domova mládeže v Jevíčku. V prázdninovém týdnu mohou studenti všech typů středních
škol prožít týden zajímavých diskusí a přednášek předních odborníků (nejen) z Univerzity Palackého.