Czy istnieje kandydat na naturalny problem w ?

Chcę wiedzieć, czy niejednorodność pomaga w praktyce funkcji obliczeniowych. Łatwo jest pokazać, że istnieją funkcje w , weź dowolną funkcję nieobliczalną i rozważ język { }, który wyraźnie ma proste niejednorodne obwody , ale w ogóle nie da się go obliczyć jednolicie, ale to nie są funkcje, którymi się interesuję.$P/poly - P$$f$$0^{f(n)}:n\in \omega$

Czy istnieje funkcja, o której wiemy, że można ją obliczyć nierównomiernie, ale nie wiemy, czy można ją obliczyć jednolicie (lub przynajmniej udowodnienie, że nie można obliczyć jednolicie, nie jest oczywiste)?

W jaki sposób można wykorzystać nierównomierność obwodów do funkcji obliczeniowych, o których nie wiadomo, że można je obliczyć jednorodnie (przy prawie takiej samej ilości zasobów)?

Zauważ, że nie chcę funkcji patologicznych, takich jak funkcje niepoliczalne wspomniane powyżej, chcę naturalnych funkcji, które ludzie są naprawdę zainteresowani komputerami i prawdopodobne jest, że mogą być lub mogłyby być obliczone jednolicie.

Edycja: Wiem, że . Więc odpowiedź, która nie jest wynikiem derandomizacji, jest dla mnie bardziej interesująca.$BPP \subseteq P/poly$

Edycja 2: Jak powiedzieli András Salamon i Tsuyoshi Ito w swoich odpowiedziach: , i istnieją problemy w , o których nie wiadomo, że są w , więc formalnie odpowiedzieli na to, o co prosiłem, ale że nie pomaga w tym, co naprawdę mnie interesuje, ponieważ powodem, dla którego są w jest możliwość twardego kodowania rzadkiego języka w obwodzie. Język, który nie jest rzadki, byłby bardziej interesujący.$Sparse \subset P/poly$$Sparse$$P$$P/poly$

Nie wiem, czy to spełnia twoje wymagania, ale blog Billa Gasarcha w lipcu 2010 r. Pyta o języki w SPARSE ∩NP, których nie uważa się za P, podając przykład z teorii Ramseya. Wszelkie takie języki należą do (P / poly) ∩NP.

W związku z tym, dla dowolnego języka L ∈NP, język T _L = {1 ⁿ : L zawiera jakiś ciąg długości n } jest w TALLY ∩NP ⊆ SPARSE∩NP ⊆ (P / poli) ∩NP. W zależności od wyboru języka L , T _L może nie mieć oczywistego powodu, aby należeć do P.

Tsuyoshi Ito elegancko rzadkie frazowanie w innej odpowiedzi nie mówi wprost, ale być może warto wskazać: każdy rzadki język jest w języku P / poly. Wtedy również każdy język tally jest w P / poly (ponieważ każdy język tally jest rzadki).

Tak więc jednym ze sposobów na znalezienie „naturalnych” języków w P / poli, ale nie w P, jest poszukiwanie „twardych” rzadkich języków. Jak zauważyłeś, „najtrudniejszymi” są nierozstrzygalne, gdy są zakodowane w rzadki sposób, na przykład jednoargumentowy. Mówiąc bardziej ogólnie, unarnie zakodowana wersja dowolnego języka spoza EXP będzie wtedy poza P. (Jeśli nie, to rozważ maszynę Turinga w czasie wykładniczym, która generuje jednoargumentowe kodowanie, skomponowaną z maszyną, która rozwiązuje powstały w rezultacie język niezakodowany w czasie który jest wielomianowy w jednostronnym kodowaniu. Jest to wykładniczy rozmiar oryginalnej instancji. Ogólna maszyna następnie działa w wykładniczym czasie.) Jakiś przydatny język z kompletnym 2-EXP może więc odpowiadać twojemu gustowi jako „naturalny” problem.

Zauważ, że rzadki, teoretyczny język Billa Gasarcha wydaje się należeć do kategorii języków skonstruowanych przez sparyfikowanie twardego języka. Jeśli ktoś koduje instancję jako potrójną liczbę dwójkową zamiast dwóch jednorzędowych i jednej dwójkowej, wówczas kolorowanie nie jest już wielomianowe, więc język nie jest oczywiście w NP.

To bardziej przypomina komentarz w odpowiedzi na zmienione pytanie (wersja 3) niż odpowiedź, ale jest zbyt długi na komentarz.

Samo wykluczenie rzadkich języków nie wystarczy, aby wykluczyć języki takie jak { x ∈ {0,1} ^* : | x | ∈ S } zamiast {1 ⁿ : n ∈ S }, gdzie S jest nieskończonym podzbiorem {0, 1, 2,…}. Chciałbym zauważyć, że rozróżnienie między przypadkiem, w którym język należy do P / poly, może być trudne, ponieważ jest on „zasadniczo rzadki” (taki jak {1 ⁿ : n ∈ S } i { x : | x | ∈ S.}) oraz przypadek, w którym język należy do P / poly z innych powodów. Problematyczne jest tutaj, jak zdefiniować termin „zasadniczo rzadki”.

Możesz zdefiniować „niezbędną rzadkość” w następujący sposób: język jest zasadniczo rzadki, jeśli można go zredukować do języka rzadkiego. Należy jednak zachować ostrożność, ponieważ w przypadku tej wielomianowej redukcji Turinga w czasie wielomianowym definicja jest równoznaczna z przynależnością do P / poly!

Oczywistą rzeczą, którą należy wypróbować, jest zastosowanie wielomianowej redukcji wielokrotności w czasie wielomianowym. Nie wiem, czy jest to równoznaczne z członkostwem w P / poly, nie mówiąc już o tym, czy P / poly zawiera jakiś język naturalny, który nie jest zasadniczo rzadki w tym znaczeniu.