Podstawy Informatyki

prof. dr hab. Marek Zaionc
dr Katarzyna Grygiel

środa 12:15 - 14:00, sala 0174

Research seminar devoted to problems related to asymptotic densities in logic, computability theory, computational logic, typed lambda calculus, logic programming, logics of programs, functional programming.

Między dokładnością a użytecznością istnieje fascynująca kraina przybliżeń. Podczas wykładu pokażemy, czym jest aproksymacja, dlaczego bez niej nie byłoby ani nowoczesnej nauki, ani komputerów, oraz jak zaskakująco często wystarcza nam odpowiedź „prawie dokładna”, by lepiej zrozumieć świat.

Jakub Wieliczko

It is shown that any recognition problem solved by a polynomial time-bounded nondeterministic Turing machine can be “reduced” to the problem of determining whether a given propositional formula is a tautology.  Here “reduced” means, roughly speaking, that the first problem can be solved deterministically in polynomial time provided an oracle is available for solving the second. From this notion of reducible, polynomial degrees of difficulty are defined, and it is shown that the problem of determining tautologyhood has the same polynomial degree as the problem of determining whether the first of two given graphs is isomorphic to a subgraph of the second. Other examples are discussed. A method of measuring the complexity of proof procedures for the predicate calculus is introduced and discussed. Throughout this paper, a set of strings1 means a set of strings on some fixed, large, finite alphabet Σ. This alphabet is large enough to include symbols for all sets described here. All Turing machines are deterministic recognition devices, unless the contrary is explicitly stated