Czy istnieją problemy bez wydajnych algorytmów, w których twierdzenia dotyczące istnienia udowodniły, że takie algorytmy muszą istnieć?

22

Czy istnieją problemy w CS, w których nie są znane wydajne algorytmy, pomimo twierdzeń o istnieniu dowodzących, że takie wydajne algorytmy muszą istnieć?

Jak nazywają się te problemy? Gdzie mogę dowiedzieć się więcej?

ds.algorithms reference-request terminology z5h
źródło
4
Myślę, że to jest istotne: en.wikipedia.org/wiki/Minor_(graph_theory)#Algorytmy
Philip White
3
Jakie jest Twoje pytanie? W tytule jest napisane „rozwiązania”, ale w treści piszesz „algorytmy”.
Marcos Villagra
6
Myślę, że lepiej byłoby, gdybyś poprosił o ciekawe / naturalne problemy, w przeciwnym razie łatwo jest zdefiniować takie problemy: weź dowolne stwierdzenie matematyczne, które nie jest znane jako prawda lub fałsz, ustaw wyjście problemu 1 (niezależnie od danych wejściowych) true i 0, jeśli jest false. Istnieją dwa bardzo proste algorytmy, które jeden z nich rozwiązuje ten problem, ale decydowanie, które w gruncie rzeczy dowodzi / obala stwierdzenie matematyczne, więc nie wiemy, który z nich rozwiązuje.
Kaveh

Odpowiedzi:

9

Jako przykład Shelby Kimmel używa metody przeciwnika w tym dokumencie, aby pokazać, że musi istnieć algorytm zapytania dla określonego problemu, dla którego nie znamy stałego rozwiązania zapytania. Robi to w szczególnie sprytny sposób, znajdując złożoność zapytania złożonego ze sobą d razy, a następnie znajdując złożoność zapytania Q kompostowanej funkcji, i zauważając, że złożoność zapytania oryginalnej funkcji jest rzędu Q 1O(1)dQ .Q1d

Artem Kaznatcheev
źródło
12

Jasne, istnieje wiele przykładów, przynajmniej w duchu twojego pytania.

Często taki wynik uzyskuje się metodą probabilistyczną . Na przykład jeden papier, który mi się podoba, który napotyka problem, dotyczy rekonstrukcji wykresów w modelu addytywnym . Tutaj autorzy pokazują, że istnieje zbiór zapytań, które będą (optymalnie) Dowiedz się wykres docelowej. Biorąc pod uwagę ten zestaw, algorytm jest wydajny. Jednak używają metody probabilistycznej, aby pokazać istnienie tego małego zestawu (dla każdego rozmiaru problemu), który będzie działał na wszystkich danych wejściowych, ale nie będzie go jawnie konstruował. Zatem najlepsze, co mogą zrobić, to po prostu przeszukanie brutalnej siły przez wykładniczą rodzinę zapytań, ponieważ nie mają one wyraźnej konstrukcji.O(dn)

Lew Reyzin
źródło
2

Nie, zawsze możesz użyć najszybszego i najkrótszego algorytmu dla wszystkich dobrze zdefiniowanych problemów . ;)

Marcus Ritt
źródło
Nie byłem całkowicie poważny, ale zauważyłem, że konstrukcja Huttera faktycznie dowodzi poprawności algorytmu. Jak myślisz, dlaczego nie odpowiada na pytanie?
Marcus Ritt,
4
@Ross Snider: oczywiście nierozstrzygalne języki wymykają się wynikowi Huttera: w końcu daje algorytm! Jednak w przeciwieństwie do wyszukiwania Levin, które wymaga, aby instancje problemowe miały weryfikowalne certyfikaty (jak problemy z wyszukiwaniem NP), wyszukiwanie Huttera nie. Wymaga jedynie sformułowania problemu w języku formalnym, który może służyć jako podstawa do wyczerpującego poszukiwania dowodów [że niektóre TM faktycznie rozwiązuje określony problem]. Ponadto Hutter / Levin nie daje nam dowodów istnienia skutecznych algorytmów dla problemu, chyba że wiemy już, że problem ma taki algorytm.
Joshua Grochow
1
@Joshua Przywołałem nierozstrzygalne języki jako przykład czegoś, czego wyszukiwanie Hutter / Levin nie mogło prawdopodobnie rozstrzygnąć (próbowałem wybrać coś oczywistego), ale które pozostaje „dobrze zdefiniowane”; jest to argument przeciwko roszczeniu postawionemu w tytule artykułu. Oczywiście starałem się przyznać, że nie przeczytałem treści, co muszę teraz zrobić.
Ross Snider
1
Czy ten algorytm jest zawartością obliczeniową równoważności konstruktywnej i klasycznej matematyki w instrukcjach typu „wszystko istnieje”?
Neel Krishnaswami,
1
@Neel Kirshnaswami: Trudno powiedzieć, ponieważ nie wiedziałem, że istnieje taka równoważność! Czy możesz podać wskaźnik?
Joshua Grochow
1

Edycja: Poniższa odpowiedź rejestruje istnienie rozwiązań dla danego problemu obliczeniowego, a nie istnienie algorytmów. Początkowo źle zinterpretowałem pytanie.

Odpowiedź

Istnieje klasa złożoności, która wychwytuje tego rodzaju problemy obliczeniowe. Jest znany jako TFNP . Zostało to zdefiniowane w tym artykule:

Nimrod Megiddo i Christos Papadimitriou. O funkcjach całkowitych, twierdzeniach o istnieniu i złożoności obliczeniowej . Theoretical Computer Science 81 (2): 317-324.

Tutaj znajdziesz problemy takie jak Trójkąt Trichromatyczny, dla którego istnienie rozwiązania jest gwarantowane przez Lemmę Spernera (definicję tego problemu można znaleźć w artykule).

Masz również następujący papier:

Christos Papadimitriou. O złożoności argumentu parzystości i innych nieskutecznych dowodach istnienia . Journal of Computer and Systems Science 48 (3), 1990.

W tym artykule znajdziesz:

  • n
  • Równowaga gier 2-osobowych.
  • Znajdź drugą ścieżkę hamiltonowską na wykresie.

Artykuł zawiera wiele przykładów tego rodzaju problemów. Dlatego polecam rzucić na to okiem.

Marcos Villagra
źródło
2
Pytanie nie dotyczy problemów z możliwymi do udowodnienia rozwiązaniami dla ich wersji decyzyjnych, ale problemów z udowodnionym istnieniem wydajnych algorytmów. To są różne rzeczy. Zgadzam się, że na pierwszy rzut oka tytuł może wprowadzać w błąd. Jednak tylko na pierwszy rzut oka.
Oleksandr Bondarenko
tak, ja też się zgadzam. Ale pytanie mnie całkowicie zwiodło. Teraz w tym przypadku odpowiedź jest myląca. Co ja robię? Czy usuwam pytanie? Lub edytuj i umieść ostrzeżenie o tym, co dokładnie odpowiada?
Marcos Villagra
Nie ma żadnych zasad dotyczących usuwania odpowiedzi, zawsze możesz zrobić to, co uważasz za właściwe. Osobiście uważam, że możesz zostawić tutaj swoją odpowiedź. Możesz umieścić oświadczenie dotyczące tego, na które dokładnie odpowiadasz.
Hsien-Chih Chang 張顯 之