Czy w teorii złożoności istnieją prawa ochrony?

Zacznę od kilku przykładów. Dlaczego tak trywialne jest pokazanie, że CVP jest w P, ale tak trudno jest pokazać LP w P; podczas gdy oba są problemami typu P-zupełnego.

Lub weźmy pierwszeństwo. Łatwiej jest wyświetlać kompozyty w NP niż liczby pierwsze w NP (co wymagało Pratta) i ostatecznie w P. Dlaczego w ogóle musiał wykazywać tę asymetrię?

Wiem, że Hilbert, potrzeba kreatywności, dowody są w NP itp. Ale to nie powstrzymało mnie od mdłości, że jest w tym coś więcej niż na pierwszy rzut oka.

Czy istnieje wymierne pojęcie „pracy” i czy istnieje „prawo zachowania” w teorii złożoności? To pokazuje, na przykład, że chociaż CVP i LP mają P-kompletność, ukrywają swoją złożoność w „różnych miejscach” - jednym w redukcji (czy CVP jest proste, ponieważ cała praca jest wykonywana w redukcji?) I inne w wyrazistości języka.

Ktoś jeszcze cierpi i ma pewne spostrzeżenia? Czy też wzruszamy ramionami i mówimy / akceptujemy, że taka jest natura obliczeń?

To jest moje pierwsze pytanie na forum: kciuki.

Edycja: CVP to problem z wartością obwodu, a LP to programowanie liniowe. Dziękuję Sadeqowi za wskazanie zamieszania.

To pytanie przyszło mi do głowy wiele razy.

Myślę, że jednym z miejsc, w których można szukać, jest teoria informacji. Oto moje spekulacje. Biorąc pod uwagę problem, możemy podać jakąś wartość entropii informacji podanej jako dane wejściowe i informacje otrzymane z algorytmu. Gdybyśmy mogli to zrobić, wówczas algorytm potrzebowałby pewnej minimalnej ilości informacji do rozwiązania tego problemu.

Jest jedna pokrewna rzecz, którą chciałem odkryć. W niektórych problemach z uzupełnianiem NP można znaleźć ograniczoną wersję w P; ze ścieżką hamiltonowską, jeśli określisz, że wykres jest DAG, istnieje algorytm czasu p, aby go rozwiązać. W przypadku innych problemów, takich jak TSP, często istnieją algorytmy czasu p, które przybliżą optymalne. Wydaje mi się, że w przypadku algorytmów o ograniczonym czasie p powinna istnieć pewna proporcjonalna zależność między przyjętymi informacjami dodatkowymi a zmniejszeniem złożoności w czasie wykonywania. W przypadku TSP nie zakładamy dodatkowych informacji, rozluźniamy precyzję, która, jak się spodziewam, będzie miała podobny wpływ na jakikolwiek algorytmiczny przyrost informacji.

Uwaga na temat przepisów konserwatorskich

We wczesnych latach XX wieku mało znany niemiecko-amerykański matematyk o imieniu Emily Noether. Między innymi Einstein i Hilbert opisali ją jako najważniejszą kobietę w historii matematyki. W 1915 r. Opublikowała tak zwane pierwsze twierdzenie Noether . Twierdzenie dotyczyło fizycznych praw zachowania i powiedział, że wszystkie prawa zachowania mają odpowiednią różnicową symetrię w układzie fizycznym. Zachowanie momentu pędu pochodzi z symetrii obrotowej w przestrzeni, zachowanie momentu pędu jest tłumaczeniem w przestrzeni, zachowanie energii jest tłumaczeniem w czasie. Biorąc pod uwagę, że aby istniało jakieś prawo zachowania złożoności w sensie formalnym, musiałaby istnieć odpowiednia symetria różniczkowa w funkcji Langragiana.

Myślę, że powodem jest logiczny system, którego używamy. Każdy system formalny ma zestaw aksjomatów i zestaw reguł wnioskowania .

Dowód w systemie formalnym jest po prostu sekwencją wzorów, tak że każdy wzór w sekwencji albo jest aksjomatem, albo jest uzyskiwany z wcześniejszych wzorów w sekwencji przez zastosowanie reguły wnioskowania. Twierdzenie o systemie formalnym jest tylko ostatnim wzorem w dowodzie.

Długość dowodu twierdzenia, przy założeniu, że jest on rozstrzygalny w systemie logicznym, zależy całkowicie od zbiorów aksjomatów i reguł wnioskowania .

Rozważmy na przykład logikę zdań, dla której istnieje kilka charakterystyk: Frege (1879), Nicod (1917) i Mendelson (1979). (Zobacz tę krótką ankietę, aby uzyskać więcej informacji.)

$\varphi \to \varphi$

Problem ten nazywa się złożonością dowodu . Cytując Beame & Pitassi :

Jedno z najbardziej podstawowych pytań logicznych jest następujące: Biorąc pod uwagę powszechnie prawdziwe stwierdzenie (tautologia), jaka jest długość najkrótszego dowodu tego stwierdzenia w jakimś standardowym systemie dowodu aksomatycznego? Logiczna wersja zdania tego pytania jest szczególnie ważna w informatyce zarówno dla udowodnienia twierdzeń, jak i teorii złożoności. Ważnymi powiązanymi pytaniami algorytmicznymi są: Czy istnieje skuteczny algorytm, który da dowód na jakąkolwiek tautologię? Czy istnieje skuteczny algorytm pozwalający uzyskać najkrótszy dowód jakiejkolwiek tautologii? Takie pytania o dowodzenie i złożoność twierdzeń stały się inspiracją dla ważnego artykułu Cooka na temat kompletności NP, zatytułowanego „Złożoność procedur dowodzenia twierdzeń”, i był rozważany jeszcze wcześniej przez Gödela w jego znanym już liście do von Neumanna.

Zastanawiałem się nad tym samym pytaniem innego dnia, kiedy odtwarzałem niektóre Wykłady Feynmana na temat fizyki, i doszedłem do lekcji 4 na temat zachowania energii. W wykładzie Feynman wykorzystuje przykład prostej maszyny, która (poprzez pewien system dźwigni, kół pasowych itp.) Obniża wagę jednej jednostki o pewną odległość x, i wykorzystuje ją do podniesienia drugiej masy o 3 jednostki. Jak wysoko można podnieść ciężar? Feynman zauważa, że ​​jeśli maszyna jest odwracalna, nie musimy nic wiedzieć o mechanizmie maszyny - możemy traktować ją jak czarną skrzynkę - i zawsze podnosi ciężar na maksymalną możliwą odległość ( x / 3 w tym przypadku).

Czy to ma analogiczne obliczenia? Idea odwracalnego obliczenia przywodzi na myśl pracę Landauera i Bennetta, ale nie jestem pewien, czy właśnie w tym sensie jesteśmy zainteresowani. Intuicyjnie, jeśli mamy algorytm dla problemu, który jest optymalny, to nie ma żadnej marnowanej „pracy” wykonywanej przy ubijaniu bitów; podczas gdy brutalne podejście do tego samego problemu wyrzucałoby cykle procesora w lewo i prawo. Wyobrażam sobie jednak, że można zbudować fizycznie odwracalny obwód dla każdego algorytmu.

Myślę, że pierwszym krokiem w podejściu do prawa zachowania złożoności obliczeniowej jest dokładne określenie, co należy zachować. Przestrzeń i czas są ważnymi wskaźnikami, ale z istnienia kompromisów czasoprzestrzennych wynika, że ​​żadne z nich samo w sobie nie będzie wystarczające jako miara tego, ile „pracy” wykonuje algorytm. Istnieją inne parametry, takie jak odwrócone głowy TM lub skrzyżowania komórek taśmy. Żadne z nich nie wydaje się być bliskie naszej intuicji co do ilości „pracy” wymaganej do przeprowadzenia obliczeń.

Drugą stroną problemu jest ustalenie, na co ta praca zostanie przekształcona. Kiedy już uzyskasz wyjście z programu, co dokładnie zyskałeś?

Kilka uwag sugerujących istnienie prawa zachowania:

$<_p$$P\ne NP$

$P=\{L| L<_p HornSAT \}$

$NP=\{L| L<_p 3SAT \}$

$CoNP=\{L| \bar L<_p 3SAT \}$

$NPC=\{L| L<_p 3SAT, 3SAT<_p L \}$

$PC=\{L| L<_p HornSAT, HornSAT<_p L \}$

$P$$P=\{L| L<_p HornSAT, \bar L <_p HornSAT \}$$P$$NP$$P=NP$

Tao sugeruje istnienie prawa zachowania trudności w matematyce: „aby udowodnić autentycznie nietrywialny wynik, trzeba gdzieś ciężko pracować”.

Twierdzi on, że trudność niektórych matematycznych dowodów sugeruje niższą granicę nakładu pracy wymaganego przez proces dowodzenia twierdzeń.