Задачата във вариант A се е оказала непреодолима за почти всички.  Аз мислех, че с даденото упътване, мнозинството ще види защо Dijkstra  от произволен връх 2-апроксимира оптималното решение, но се оказва, че почти никой не знае неравенството на триъгълника за разстоянията в граф и така упътването става безполезно.

Теоретичният въпрос във вариант А също се е оказал корав орех.  Повече от половината, бих казал,  нямат смислена дефиниция на "долна граница на сложност на задача".  Почти никой не е казал прецизно какво е дърво на вземане на решение -- а то е (неуниформен) изчислителен модел.  То изчислява, също както машината на Тюринг изчислява.


Last modified: Thursday, 30 July 2020, 6:06 PM