Czy istnieje teoria złożoności analogiczna z twierdzeniem Rice'a w teorii obliczalności?

Twierdzenie Rice'a stwierdza, że ​​każda nietrywialna właściwość zbioru rozpoznawana przez niektóre maszyny Turinga jest nierozstrzygalna.

Szukam teoretycznego złożoności twierdzenia typu Rice, które mówią nam, które nietrywialne właściwości zbiorów NP są trudne do rozwiązania.

Udowodnienie takiej złożoności teoretycznej wersji twierdzenia Rice'a było dla mnie motywacją do studiowania zaciemnienia programu.

Twierdzenie Rice'a mówi w istocie, że trudno jest zrozumieć funkcje obliczane przez programy, biorąc pod uwagę program. Przyczyną tych problemów jest jednak to, że są one nieskończone. Nawet przy jednym wejściu program nigdy się nie zatrzyma i musimy rozważyć, co program robi na nieskończenie wielu wejściach.

Skończona wersja twierdzenia Rice'a poprawiłaby wielkość wejściową i czas działania programu i powiedziałaby, że program jest trudny do zrozumienia. Po ich naprawieniu możesz równie dobrze postrzegać program jako obwód logiczny. Jakie właściwości funkcji obliczonej przez obwód logiczny są trudne do obliczenia? Jednym z przykładów jest `` nie zawsze 0 '', czyli problemy z całkowitą satysfakcją z NP. Ale w przeciwieństwie do twierdzenia Rice'a, istnieją pewne właściwości, które są nietrywialne, ale łatwe, nawet bez zrozumienia obwodu. Zawsze możemy wiedzieć, że: funkcja obliczona przez obwód ma ograniczoną złożoność obwodu (wielkość obwodu). Ponadto zawsze możemy ocenić obwód na wybranych wejściach.

$f_C$$n$$|C|$$f_C$$n$$x$$x$$f(0..0)=1$$f_C$

O ile mi wiadomo, pytanie to jest otwarte, nasze zamierzone podejście zostało wykluczone. Mieliśmy nadzieję to udowodnić, pokazując, że możliwe jest kryptograficznie bezpieczne zaciemnianie programu. Jednak Boaz udowodnił coś przeciwnego: że było to niemożliwe. To domyślnie pokazuje, że dostęp czarnej skrzynki do obwodów jest bardziej ograniczony niż pełny dostęp do opisu obwodu, ale dowód nie jest konstruktywny, więc nie mogę nazwać żadnej właściwości jak wyżej, która jest łatwa z uwagi na opis obwodu, ale nie z czarnym dostęp do skrzynki. Interesujące jest (przynajmniej dla mnie), czy taka właściwość mogłaby zostać odwrócona na podstawie naszej pracy.

Oto odniesienie: Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang: O (Im) możliwościach zaciemniania programów. CRYPTO 2001: 1-18

Przez lata udowodniono kilka takich twierdzeń. Ostatnio podjęto wysiłki w celu ustalenia twierdzeń w stylu „ryżu” dotyczących problemów w obwodach. (Naturalne jest zastąpienie „maszyn” „obwodami”. Po wykonaniu tej czynności całkowita liczba możliwych danych wejściowych zostaje ustalona, ​​więc nie występują problemy z nierozstrzygalnością.) Dwa odniesienia:

Bernd Borchert, Frank Stephan: Poszukiwanie analogu twierdzenia Rice'a w teorii złożoności obwodu. Matematyka Log. Pytanie 46 (4): 489–504 (2000)

Lane A. Hemaspaandra, Jörg Rothe: Drugi krok w kierunku teorii złożoności analogów twierdzenia Rice'a. Teoria Comput. Sci. 244 (1-2): 205–217 (2000)

Oto przykładowy wynik: „Każda niepusta właściwa właściwość zliczania obwodów jest bardzo trudna”. Możesz przeczytać dokumenty dla definicji, ale z grubsza oznacza to, że każda właściwość zależna od liczby spełniających przypisań do obwodu jest trudna dla klasy UP (stąd trudna do rozwiązania).

Istnieją również starsze prace nad teoretycznie złożonymi wersjami twierdzenia Rice'a, w innym duchu. Nie jestem z tym zaznajomiony, ale przytaczają je powyższe artykuły.

$NP$$NP$$NP$