Одељење за математику, 6. децембар 2013.

• 02. Децембар, 2013
• Коментари (0)

Наредни састанак семинара биће одржан у петак, 6. децембар 2013. са почетком у 14 часова у сали 301ф, Математичког института САНУ.

Предавач: Петар Марковић, Департман за математику и информатику ПМФ, Нови Сад

Наслов предавања: УВОД У ДЕСКРИПТИВНУ ТЕОРИЈУ РАЧУНСКЕ СЛОЖЕНОСТИ

Садржај: Године 1974. Р. Фагин је доказао да је скуп својстава изразивих у егзистенцијалном фрагменту логике другог реда једнак класи рачунске сложености НП (недетерминистички полинимна).

Од те теореме почиње област рачунске сложености која повезује разне логичке системе са класама рачунске сложености.

Из тачке гледишта предавача (приученог аматера у овој теми), изгледа да се ова област примарно развијала у два правца: "улепшавање класе НП" које је ишло ка налажењу све рестриктивнијих логичких система који се такође поклапају са класом НП, или бар имају непразан пресек са сваком класом сложености унутар НП, и "превођење логике на језик теорије сложености" где се различити природни фрагменти логике првог и другог реда на сличан начин као код Фагина повезују са класама рачунске сложености.

Први правац, свакако, има за мотивацију напад на миленијумски проблем $P=?NP$, док је други дао једну богату менажерију нових класа сложености са којима се данас ради, те је и један од најпознатијих прегледних интернет сајтова о овој области назван "Complexity Zoo".

Даћемо кратак преглед одабраних резултата у оба правца од 1974. до данас.