Ograniczenie pytań progowych do pytań skończoności

Zwykle łatwiej jest uzasadnić rachunek różniczkowy, w którym ograniczeniem jest skończoność obliczeń, a nie próg taki jak „obliczalny w wielomianowym czasie”.

Na przykład w teorii języków formalnych, zamiast używać aby scharakteryzować aperiodic monoïd, łatwiej jest używać profinite wyrazów, aby .x ω + 1 = x $\exists n. x^{n+1} = x^n$$x^{\omega+1} = x^{\omega}$

W teorii złożoności jedyną znaną mi techniką, która jest z tym związana, jest sztuczka wypełniająca, na przykład łącząca problem P vs NP z EXPTIME vs NEXPTIME. Ale naturalnym nieskończonym odpowiednikiem pytań złożoności byłyby pytania obliczeniowe ”.

Czy istnieją wyniki, które łączą złożoność z pytaniami związanymi z obliczalnościami przy użyciu pewnego kodowania, tak że próg zasobów teorii złożoności staje się kwestią skończoności obliczeń w teorii obliczalności?

Sipser udowodnił, że nieskończonej parzystości nie można obliczyć za pomocą (nieskończonego) obwodu o dowolnej stałej głębokości, co można postrzegać jako rozgrzewkę do wyniku, w którym PARYSTOTNOŚĆ nie występuje w .$AC^0$

Istnieją również wyniki i próby potwierdzenia dolnych granic złożoności dowodu przy użyciu niestandardowych modeli (niektóre wyniki Ajtai i Krajicek. Patrz zwłaszcza „Forcing with Random Variables and Proof Complexity”, dostępny w Cambridge Press, ale także szkic dostępne online ). Podstawową ideą jest zbudowanie niestandardowego modelu arytmetyki, w którym stwierdzenie jest fałszywe w modelu (zamiast „prawdziwego, ale bez krótkich dowodów”), a następnie, na podstawie właściwości modelu, wywnioskować, że odpowiednia sekwencja skończona instrukcje w niektórych systemach nie mają dowodów wielomianowych.

Nie jestem pewien, ale mam wrażenie, że często wyniki te w pewnym sensie „ukrywają asymptotyki pod maską”, tak że nie jest to redukcja od progu do skończoności, ponieważ jest to nowy język matematyczny, w którym „fałsz” w nowy język odpowiada „bez krótkich dowodów” w starym języku. Nie oznacza to, że nowy język nie zapewnia nowego, użytecznego punktu widzenia, ale nie jestem pewien, czy tego właśnie szukasz.

Pola złożoności opisowej i ukrytej złożoności można postrzegać jako takie podejście. Oba przekształcają ograniczenie zasobów (takie jak lub ) w możliwość wyrażenia problemu w logicznym formalizmie (dla złożoności opisowej) lub w konkretnym języku programowania (dla ukrytej złożoności).$P$$NP$

Zatem nie jest on sam w sobie związany z obliczeniami nieskończonymi, ale raczej z wyrażalnością problemu w danym modelu. Jest jednak bliski w tym sensie, że zamienia problem ilościowy w jakościowy.