Czy istnieje kompletny problem dla klasy rozstrzygających problemów Turinga?

Języki, takie jak są przy wielu redukcjach. To banalne, aby zobaczyć, że ma również kompletne problemy. S. Schmitz [1] rozważa niektóre klasy pomiędzy a . Stanowią one kompletne problemy dla tych klas w ramach specjalnie spreparowanych redukcji. $\text{HALT}_{TM}$ $\textsf{RE-complete}$ $\text{co-RE}$ $\text{ELEM}$ $\text{REC}$

Czy istnieją całkowite problemy dla (aka ) w stosunku do słabszych redukcji? Redukcje Turinga są nieodpowiednie, ponieważ są w stanie wykonać całą pracę. Czy powinniśmy oczekiwać, że takie redukcje zostaną wymyślone, czy nie ( np. Redukcje wielokrotne, które ograniczają się do prymitywnej rekurencji)? $\textsf{R} = \textsf{RE} \cap \textsf{co-RE}$ $\textsf{REC}$

[1] Sylvain Schmitz Complexity Hierarchies Beyond Elementary 2013 http://arxiv.org/abs/1312.5686

computability reductions turing-completeness recursion-theory mdxn
źródło

To pytanie wydaje się trochę proste, ale profesor i ja go nie rozumiemy. Nie zdziwiłbym się, gdyby odpowiedź była oczywista. Przepraszam, jeśli tak jest. Mimo to miło będzie mieć odpowiedź gdzieś w Internecie.

mdxn

Każdy nietrywialny problem rekurencyjny jest kompletny przy rekurencyjnych redukcjach wielokrotnych. Szukasz słabszych obniżek?

Yuval Filmus

@YuvalFilmus: Tak, jestem.

mdxn

@YuvalFilmus Podam trochę więcej informacji. Rozważmy przypadek z

. Patrząc na kompletność P, zwykle bierzemy pod uwagę słabsze redukcje, takie jak przestrzeń logiczna lub redukcje pierwszego rzędu. Jeśli zdefiniowaliśmy kompletność P za pomocą wielomianowych redukcji wielokrotnych jeden, wówczas napotkamy podobną sytuację, którą przedstawisz (wiadomo, że obniżenie FO jest zdecydowanie słabsze). Możemy sprawić, że redukcja wykona prawie wszystkie obliczenia zamiast identyfikowania kompletnych problemów w owocny sposób.

P

$\textsf{P}$

mdxn

Odpowiedzi:

Zasadniczo klasa mająca pełny problem w ramach ładnej klasy redukcji oznacza, że można ją wyliczyć. nie jest wyliczalny, dlatego nie ma pełnego problemu w odniesieniu do niezłej klasy redukcji. $\mathsf{R}$

Oto argument:

Załóżmy, że jest kompletnym problemem dla . Zatem żadnego problemu w mogą być uzyskane z redukcji (powiedzmy wielomianu razem wiele-onu redukcje) w połączeniu z . Możemy computably wyliczyć redukcje, dlatego możemy computably enumerate . Ale nie jest wyliczalne (w przeciwnym razie moglibyśmy przekątnie). $A$ $\mathsf{R}$ $\mathsf{R}$ $A$ $\mathsf{R}$ $\mathsf{R}$

W literaturze poszukaj zestawu całkowitych funkcji rekurencyjnych / obliczalnych .

Kaveh
źródło

Witaj ponownie, Kaveh! Dobrze cię znowu widzieć!

David Richerby,

Dlaczego policzone są ograniczenia czasowe?

Ariel

Tak, wspomniałeś o tym w poście :) jednak jestem trochę zdezorientowany, czy mógłbyś rozwinąć wyliczenie?

Ariel

n^{k} + k

$n^k+k$