Czy istnieją problemy, których średnia złożoność przypadków jest taka sama jak ich najgorsza złożoność? Jakie są podstawowe właściwości tych problemów, które pozwalają zredukować najgorszy przypadek do przeciętnego przypadku?
11
Czy istnieją problemy, których średnia złożoność przypadków jest taka sama jak ich najgorsza złożoność? Jakie są podstawowe właściwości tych problemów, które pozwalają zredukować najgorszy przypadek do przeciętnego przypadku?
Odpowiedzi:
Ten rodzaj problemu był przedmiotem wielu badań. Możesz znaleźć referencje, przeglądając losowo samoczynną redukcję w Google, a artykuł w Wikipedii jest dobrym miejscem do rozpoczęcia czytania. Nadal istnieje wiele powiązanych otwartych pytań.
źródło
Wpis w Wikipedii, do którego nawiązał Peter, wymienia kilka ważnych przykładów problemów, które mają najgorsze i średnie przypadki redukcji przypadków, takie jak trwałe. Najkrótszy problem wektorowy (podobnie jak powiązane problemy z siecią) jest kolejnym ważnym przykładem, patrz artykuł Ajtai i co potem po nim (prace Regev, Micciancio, Peikert, ...).
Jedną z jedynych ogólnych uwag, jakie mamy na temat problemów z redukcją przypadków najgorszych do średnich jest następująca (rozpoczęta od pracy Feigenbauma i Fortnowa ): (Przynajmniej w przypadku redukcji nieadaptacyjnych) problemy te prawdopodobnie nie będą występować kompletne do klas, które (prawdopodobnie) nie są zamknięte w ramach dopełniacza (np. prawdopodobnie nie będą kompletne NP).
źródło