Alternatywne pojęcie złożoności oparte na luce między brutalną siłą a najlepszym algorytmem?

Zwykle wydajne algorytmy mają wielomianowe środowisko wykonawcze i wykładniczo dużą przestrzeń rozwiązania. Oznacza to, że problem musi być łatwy w dwóch aspektach: po pierwsze, problem można rozwiązać w wielomianowej liczbie kroków, a po drugie, przestrzeń rozwiązania musi być bardzo ustrukturyzowana, ponieważ środowisko wykonawcze jest tylko polilogarytmiczne pod względem liczby możliwych rozwiązań.

Czasami jednak te dwa pojęcia się różnią, a problem jest łatwy tylko w pierwszym tego słowa znaczeniu. Na przykład, powszechną techniką w algorytmach aproksymacyjnych i sparametryzowanej złożoności jest (z grubsza) udowodnienie, że przestrzeń rozwiązania można faktycznie ograniczyć do znacznie mniejszego rozmiaru niż naiwna definicja, a następnie użyć brutalnej siły, aby znaleźć najlepszą odpowiedź w tej ograniczonej przestrzeni . Jeśli możemy a priori ograniczyć się do, powiedzmy, n ^ 3 możliwych odpowiedzi, ale nadal musimy sprawdzić każdą z nich, to w pewnym sensie takie problemy są nadal „trudne”, ponieważ nie ma lepszego algorytmu niż brutalna siła.

I odwrotnie, jeśli mamy problem z podwójnie wykładniczą liczbą możliwych odpowiedzi, ale możemy go rozwiązać tylko w wykładniczym czasie, to chciałbym powiedzieć, że taki problem jest „łatwy” („ustrukturyzowany” może być lepszy słowo), ponieważ środowisko wykonawcze jest tylko logiem wielkości obszaru rozwiązania.

Czy ktoś zna jakieś dokumenty, które uważają coś w rodzaju twardości opartej na przepaści między wydajnym algorytmem a brutalną siłą lub twardością w stosunku do wielkości przestrzeni rozwiązania?

Jednym z problemów związanych z sformalizowaniem pytania jest to, że wyrażenie „przestrzeń rozwiązania dla problemu A” nie jest dobrze zdefiniowane. Definicja przestrzeni rozwiązania wymaga algorytmu weryfikującego , który przy danej instancji i rozwiązaniu kandydującym sprawdza, czy rozwiązanie jest poprawne. Następnie przestrzenią rozwiązania instancji wrt do weryfikatora jest zestaw rozwiązań kandydujących, dzięki którym dane wyjściowe weryfikatora są „poprawne”.

Weźmy na przykład problem SAT0: biorąc pod uwagę formułę boolowską, czy spełnia go przypisanie wszystkich zer? Ten problem występuje trywialnie w czasie wielomianowym, ale jego przestrzeń rozwiązania może się bardzo różnić, w zależności od używanego weryfikatora. Jeśli Twój weryfikator zignoruje rozwiązanie kandydujące i po prostu sprawdzi, czy wszystkie zera działają na instancji, wówczas „przestrzeń rozwiązania” dla dowolnej instancji SAT0 na tym weryfikatorze jest trywialna: wszystkie możliwe rozwiązania. Jeśli weryfikator sprawdzi, czy rozwiązanie kandydujące jest zadowalającym zadaniem, przestrzeń rozwiązania instancji SAT0 może być naprawdę złożona, prawdopodobnie tak złożona, jak przestrzeń rozwiązania dowolnej instancji SAT.

$t(n,k)$$n$$k$$n$$k$$O(2^k t(n,k))$

$O(2^k t(n,k))$$2^n$

Artykuł pokazuje kilka interesujących konsekwencji ulepszenia w wyszukiwaniu brutalnej siły niektórych problemów. Nawet udoskonalenie w wyszukiwaniu metodą „brute-force” „przestrzeni rozwiązań wielomianowych” miałoby interesujące konsekwencje.

Jak poradziłbyś sobie z typowymi problemami z programowaniem dynamicznym? Często zdarza się, że przestrzeń rozwiązań optymalnych jest wielomianowo ograniczona, ale przestrzeń rozwiązań nie. Wydaje się więc, że „łatwym” w twoim znaczeniu, ponieważ czas działania jest logarytmiczny w przestrzeni rozwiązań, ale w twoim znaczeniu „trudny”, ponieważ działa „brutalnie” na wszystkie potencjalnie optymalne rozwiązania.

Perspektywa wydaje się zakładać pewne rzeczy, takie jak skończoność przestrzeni rozwiązań.

Pomyśl na przykład o problemie generowania teselacji Voronoi z zestawu punktów wejściowych. Tutaj jest nieskończenie duża przestrzeń rozwiązania, ponieważ każdy punkt na krawędziach diagramu jest krotką liczb rzeczywistych. Jednak rozwiązanie można osiągnąć w O (n log (n)) w liczbie punktów wejściowych (dla płaszczyzny).

Powiązane są problemy dopuszczające algorytmy z opóźnieniem wielomianowym . Pierwsze rozwiązanie, a następnie każde kolejne, można wygenerować w czasie wielomianowym. Johnson, Yannakakis i Papdimitriou omawiają te ramy w kontekście innych możliwych luk (takich jak całkowity czas wielomianowy): O generowaniu wszystkich maksymalnych niezależnych zbiorów , listach przetwarzania informacji 27 , 119–123, 1988.