Problemy decyzyjne itd. ...

Lista zagadnie« egzaminacyjnych

Poni»ej przedstawiam (jeszcze niekompletn¡) list¦ twierdze« na egzamin. Egzamin b¦dzie ustny:

student informuje mnie na wst¦pie, które twierdzenia potra udowodni¢. Liczba tych twierdze« de-

niuje maksymaln¡ ocen¦ jak¡ mo»na dosta¢ (4 twierdzenia  ocena dostateczna, 5  plus dostateczna, 6

 dobra, 7  plus dobra, 8  bardzo dobra; dla osób, które udzielaj¡ si¦ na ¢wiczeniach liczba twierdza«

na odpowiednie oceny mo»e zosta¢ obni»ona). Nast¦pnie prosz¦ o przedstawienie dowodu jednego-

dwóch zadeklarowanych twierdze«. W czasie prezentacji dowodu mo»na oczywi±cie mie¢ notatki, ale

nale»y ich u»ywa¢ z umiarem. Kiepska prezentacja oczywi±cie powoduje obni»enie oceny.

(1) Speªnialno±¢ C

1

(logika z jedn¡ zmienn¡ i kwantykatorami zliczaj¡cymi) jest NP-zupeªna (Tw.

9 w Notatkach, [1]).

(2) Nierozstrzygalno±¢ ∀

3

∃

, ∀∃∀ (Tw. 19, 20).

(3) Problem speªnialno±ci dla FO

2

z dwiema relacjami przechodnimi jest nierozstrzygalny (Tw. 22).

(4) Wªasno±¢ modelu wykªadniczego dla logiki FO

2

(Tw. 23, [2]).

(5) Problem speªnialno±ci dla unarnego FO

2

w porz¡dkach liniowych jest w NEXPTIME (Tw. 25,

[3]).

(6) Problem speªnialno±ci dla FO

2

z relacj¡ równowa»no±ci jest w NEXPTIME (Tw. 26, [4]).

(7) Speªnialno±¢ C

2

jest rozstrzygalna (Tw. 28, [5]).

(8) Wªasno±¢ modelu sko«czonego dla klasy Gödla  dowód probabilistyczny (Tw. 33, [6]).
(9) Nierozstrzygalno±¢ klasy Gödla z równo±ci¡ (Tw. 34, [7]).

(10) Twierdzenie Hennessy'ego-Milnera (Tw. 54)
(11) Wªasno±¢ modelu sko«czonego dla logiki modalnej, dowód metod¡ ltracji (Tw. 62).
(12) Problem speªnialno±ci dla logiki modalnej jest PSPACE-zupeªny.
(13) Speªnialno±¢ GF

2

jest EXPTIME-trudna ([8]).

(14) Problem speªnialno±ci dla GF jest w 2EXPTIME ([8]).
(15) Wªasno±¢ modelu sko«czonego dla GF z dowodem tw. Herwiga (przynajmniej w wersji dla

grafów) ([8], [9]).

(16) Rozstrzygalno±¢ i NEXPTIME-zupeªno±¢ problemu speªnialno±ci logiki GF

2

+EG (relacje rów-

nowa»no±ci w star»nikach).

(17) Rozstrzygalno±¢ problemu sko«czonej speªnialno±ci logiki GF

2

+EG.

Emanuel Kiero«ski

Literatura

[1] Iana Pratt-Hartmann. On the Computational Complexity of the Numerically Denite

Syllogistic and Related Logics. 2008.

http://arxiv.org/abs/cs/0701039

[2] Erich Grädel, Phokion Kolaitis, Moshe Vardi, On the Decision Problem for Two-Variable

First-Order Logic. 1997.

http://www.logic.rwth-aachen.de/pub/graedel/basl.ps

[3] Martin Otto, Two-Variable First-Order Logic over Ordered Domains. 2001.

http://www.mathematik.tu-darmstadt.de/\~{}otto/papers/fotord.ps.

[4] E.K., Martin Otto, Small Substructures and Decidability Issues for First-Order Logic

with Two Variables. 2005.

http://www.ii.uni.wroc.pl/~kiero/LICS05j.ps

1

[5] Erich Grädel, Martin Otto, Eric Rosen Two-Variable Logic with Counting is Decidable.

1997.

www.logic.rwth-aachen.de/pub/graedel/gorc2.ps

[6] Yuri Gurevich, Saharon Shelah, Random models and the Gödel case of the decision

problem. 1983.

http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=

Display&handle=euclid.jsl/1183741419

[7] W.D. Goldfarb, The unsolvability of the Gödel class with Identity. 1984.

http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=

Display&handle=euclid.bams/1183551422

[8] Erich Grädel, On the Restraining Power of Guards. 1997.

http://www.logic.rwth-aachen.de/pub/graedel/Gr-jsl99.ps

[9] Bernhard Herwig, Daniel Lascar, Extending Partial Automorphisms and Pronite To-

pology on Free Groups http://home.mathematik.uni-freiburg.de/herwig/papers/

epfree.ps

2