Czy istnieją rozstrzygalne problemy, dla których w przypadku braku algorytmu nie możemy ustalić granic czasowych?

Czy istnieją rozstrzygalne problemy, takie że dla żadnego algorytmu, który nie rozwiązałby problemu, możemy wyznaczyć limit czasowy jako funkcję długości n instancji wejściowej?

Doszedłem do tego pytania, ponieważ myślałem o następujących kwestiach:

Załóżmy, że mamy rekurencyjnie wymienny, ale nierozstrzygalny problem. Załóżmy dalej, że jestem przyczyną problemu „tak”. Następnie, dla żadnego algorytmu, który identyfikowałby „problem” - przyczyny problemu, możemy wyznaczyć czas określony jako wielkość n I. Gdybyśmy mogli podać taki termin, moglibyśmy zdecydować o problemie, tak jak moglibyśmy po prostu wyciągnij wniosek, że jestem przekroczeniem terminu „nie”.

Ponieważ nie możemy wyznaczyć terminu na rekurencyjnie wyliczalne, nierozstrzygalne problemy (na czas obliczeń dla substancji „tak”), zastanawiałem się, czy istnieją również problemy, które można rozstrzygnąć, dla których nie możemy wyznaczyć terminu.

Dla każdego algorytmu który kończy się na klasie danych wejściowych , możemy zdefiniować funkcję jego czasów działania: gdzie to klasa danych wejściowych o długości a jest algorytmem czasowym wymaganym do zakończenia na . Oczywiście ta definicja jest niezadowalająca, ponieważ odnosi się do algorytmu, ale pokazuje istnienie takiej funkcji. Pozostaje pytanie, czy istnieje zwięzła reprezentacja (i uważam, że o to prosiliście).$A$$\mathsf{In}$

Jeśli użyjemy prostych terminów algebraicznych (bez jakiejkolwiek rekurencji) jako definicji zwięzłej, to myślę, że odpowiedź brzmi: nie. Istnieją problemy, które można rozwiązać, ale których złożoność jest nieelementowa. Oznacza to, że nie istnieje stos w postaci który ogranicza czas wykonania algorytmu dla problemu o rozmiarze n.$2^{2^{2^{2^{\dots^n}}}}$

Mam nadzieję, że dobrze zrozumiałem twoje pytanie.

Jest to nieco inne podejście do twojego pytania niż do Marcusa, ale w świetle twojego wyjaśnienia, jak pomyślałeś o tym pytaniu, może być ono bliższe temu, czego szukasz.

Czasami można udowodnić, że problem jest rozstrzygalny, bez możliwości przedstawienia algorytmu. Najbardziej znanym przykładem tego rodzaju rzeczy jest praca Robertsona i Seymoura na nieletnich grafach, która pokazuje, że o każdej dziedzicznej właściwości grafu można decydować w czasie wielomianowym, sprawdzając obecność odpowiedniej skończonej listy niedozwolonych nieletnich. Ich dowód pokazuje tylko, że istnieje skończona lista zakazanych nieletnich, ale nie zapewnia przepisu na znalezienie tej listy.

Nie jestem ekspertem w tej dziedzinie, więc nie znam od razu konkretnego przykładu dziedzicznej właściwości graficznej, dla której nie możemy przedstawić algorytmu, ponieważ nie znamy listy zakazanych nieletnich i nie znamy żadnego innego sposobu na rozwiązać problem, ale podejrzewam, że takie przykłady istnieją. (I możemy ograniczyć czas do znalezienia przykładu, jeśli istnieje, ponieważ wiemy, że na świecie jest co najwyżej 8 miliardów ludzi, aw najgorszym przypadku moglibyśmy zapytać ich wszystkich!)

Jedno dodatkowe Uwaga: Ponieważ wiemy, że sprawdzanie małoletniego można zrobić w czas, można argumentować, że we wszystkich przypadkach dostarczonych przez algorytm Robertson-Seymour, że nie mają „związany” z czasu pracy. Argumentowałbym jednak, że jest to rodzaj oszustwa, jeśli nie jesteśmy związani ze stałą.$O(n^3)$$O(n^3)$

Żeby dodać inną perspektywę, przypomnę, że nie każdy problem ma „wewnętrzną” złożoność, która jest prawdopodobnie najbardziej interesującą i w jakiś sposób zaniedbaną konsekwencją twierdzenia Blum o przyspieszeniu.

Zasadniczo twierdzenie to stwierdza, że ​​naprawiono pożądane przyspieszenie g, zawsze możesz znaleźć problem obliczeniowy P, taki że dla każdego programu rozwiązującego P istnieje inny program, który wciąż rozwiązuje P i działa g-razy szybciej niż poprzedni.

Dlatego w przypadku tego rodzaju problemów nie można ustalić terminu. Niesamowity i dość zagadkowy wynik. Oczywiście P ma bardzo dużą złożoność.

Teoretycznym aspektem twojego pytania zajmuje się Markus. Mówiąc prościej, interesującym sposobem na zrozumienie twojego pytania jest: czy istnieją rozstrzygające problemy, dla których nie znamy żadnego terminu?

Odpowiedź brzmi tak: na przykład może się zdarzyć, że masz pół-algorytm dla wystąpień TAK problemu i pół-algorytm dla NIE wystąpień. To daje rozstrzygalność twojego problemu, ale nie ma ograniczenia czasowego.

Oto ogólny przykład: załóżmy, że masz system aksjomatyczny, który pozwala ci udowodnić wszystkie prawdziwe tożsamości w jakiejś algebrze. Co więcej, wiesz, że fałszywej tożsamości zawsze towarzyszy skończona struktura.

Następnie masz następujący algorytm, aby zdecydować, czy tożsamość jest prawdziwa: wyliczyć w równoległych dowodach i strukturach skończonych i zatrzymać, gdy znajdziesz dowód na lub strukturę świadczącą o tym że fałszywy. To daje poprawny algorytm, ale nie złożoność związana, chyba że można związany rozmiaru dowodów i struktur skończonych w stosunku do .ja ja $I$$I$$I$$I$

Przykładem tego jest afiniczna logika liniowa (LLW): wiadomo, że jest ona kompletna dla wieży [1], ale przez pewien czas nie były znane żadne granice i wykazano jedynie rozstrzygalność, wykorzystując między innymi technikę modelu skończonego [2] .

Bibliografia:

[1] Nie elementarne zawiłości dla rozgałęzień VASS, MELL i rozszerzeń. Ranko Lazic i Sylvain Schmitz. CSL-LICS 2014

[2] Właściwość modelu skończonego dla różnych fragmentów logiki liniowej. Yves Lafont, J. Symb. Logika. 1997

jak twierdzą inni, pytanie nie zostało sformułowane w sposób pozwalający uniknąć banalnej odpowiedzi, jednak istnieją pewne pojęcia w TCS i teorii liczb, które są powiązane / podobne.

1) w twierdzeniach o hierarchii czasu i przestrzeni wymagana jest koncepcja funkcji „konstruowalnych w czasie” i „konstruowalnych w przestrzeni” . istnieją funkcje niemożliwe do konstruowania w czasie i niemożliwe do zbudowania w przestrzeni, które prowadzą do nietypowych właściwości znalezionych w twierdzeniach Bluma, takich jak twierdzenia o „przerwie, przyspieszeniu”. większość (wszystkich?) standardowych klas złożoności jest definiowana w kategoriach funkcji przestrzennych i czasowych.

2) funkcja ackerman jest całkowicie rekurencyjna, ale nie prymitywna rekurencyjna, co ma wpływ na jej czas. pierwotne funkcje rekurencyjne w pewnym sensie reprezentują „podstawowe” operacje matematyczne.

3) istnieją tomy o sekwencjach teorii liczb, których nie da się obliczyć w arytmetyce peano, które można interpretować jako tworzenie granic czasowych, których nie da się obliczyć, takich jak sekwencja Goodsteina lub thms Paryża- Harringtona