Teoria złożoności, gdy wyrocznia jest częścią danych wejściowych

Najczęstszy sposób, w jaki wyrocznie występują w teorii złożoności, jest następujący: Stała wyrocznia jest udostępniana, powiedzmy, maszynie Turinga z pewnymi ograniczonymi zasobami, i jedna bada, w jaki sposób wyrocznia zwiększa moc obliczeniową maszyny.

Istnieje jednak inny sposób, w jaki czasami zdarzają się wyrocznie: jako część danych wejściowych . Załóżmy na przykład, że chcę przestudiować algorytmy do obliczania objętości danego wielowymiarowego polytopa. Klasycznie polytop musiałby zostać określony poprzez podanie listy jego aspektów lub innej wyraźnej reprezentacji. Możemy jednak postawić problem obliczania objętości polytopu określonej przez wyrocznię objętościową, która przyjmuje współrzędne punktu w przestrzeni jako dane wejściowe i wyjściowe „tak” wtedy i tylko wtedy, gdy dany punkt znajduje się wewnątrz wielobiegunu. Następnie możemy zapytać, jakie zasoby obliczeniowe są potrzebne do obliczenia objętości podanego w ten sposób polytopa. W tym konkretnym przypadku mamy bardzo ładny schemat wielomianowego aproksymacji czasu Dyera, Frieze'a i Kannana oraz, co ciekawe z teorii teorii złożoności, dowód, że losowość pomaga w istotny sposób dla tego problemu, ponieważ żaden algorytm deterministyczny nie może działają tak samo jak algorytm Dyer-Frieze-Kannan.

Czy istnieje systematyczny sposób badania teorii złożoności problemów, w których wyrocznie są dostarczane w ramach wkładu? Czy w jakiś sposób sprowadza się to do zwykłej teorii klas złożoności z wyroczniami? Domyślam się, że nie, a ponieważ istnieje zbyt wiele różnych sposobów dostarczenia wyroczni w ramach wkładu, każdy problem tego rodzaju musi być rozwiązywany ad hoc. Byłbym jednak szczęśliwy, gdybym udowodnił, że się mylę w tej kwestii.

Nazywa się to teorią złożoności typu 2. Jest artykuł Cooka, Impagliazzo i Yamakamiego, który ładnie wiąże go z teorią ogólnych wyroczni.

To musi być daleka od pełnej odpowiedzi, ale mam nadzieję, że wskazuje na niektóre miejsca do obejrzenia.

Problemy, w których część danych wejściowych jest podawana jako wyrocznia, są czasem nazywane problemami z danymi niejawnymi . Jest to wygodny model, np. Podczas badania probabilistycznie sprawdzalnych dowodów .

Ważnym obszarem badań nad problemami z niejawnymi danymi wejściowymi jest teoria złożoności zapytań , w której złożoność jest mierzona wyłącznie liczbą zapytań do wyroczni wejściowej, ignorując ilość obliczeń między zapytaniami. Wiele klas złożoności ma swoje odpowiedniki w złożoności zapytań, a rozdzielenie klas złożoności w złożoności zapytań często implikuje separację wyroczni między odpowiednimi klasami w złożoności obliczeniowej.

Nie znam badań klas złożoności problemów z niejawnym wkładem (a nie pojedynczych problemów), biorąc pod uwagę koszty obliczeń, ale pewnie niektórzy to wiedzą.

Model, w którym dane wejściowe są dostarczane jako wyrocznia, jest badany w teorii obliczalności i analizie obliczeniowej. Jednym z modeli, które wydają się zbliżone do tego, co chcesz, jest model TTE (Efektywność typu drugiego). Dobrym odniesieniem jest książka Klausa Weihraucha „ Analiza obliczeniowa ”. Mówi także krótko o złożoności w rozdziale 7.

Książka Ker-I Ko „ Computational Complexity of Real Functions ” omawia inny model dostępu do wyroczni, który wydaje się bardziej odpowiedni dla złożoności. Kwestie dotyczące reprezentacji obiektów wyższego typu i sposobu dostępu do wyroczni to delikatne sprawy. Zobacz na przykład najnowszy artykuł Stephena A. Cooka i Akitoshi Kawamury „ Teoria złożoności dla operatorów w analizie ” z STOC 2010 i jego pracę doktorską . Jednym z głównych problemów jest to, że aby model był rozsądny, należy dać maszynie wystarczająco dużo czasu na przetworzenie odpowiedzi z wyroczni (w przeciwnym razie nie można nawet obliczyć operatora aplikacji). W przypadku czasu wielomianowego i przestrzeni wielomianowej można to zrobić za pomocą wielomianów wyższego rzędu opartych na Stephen A. Cook i Bruce M. Kapron 'Nowa charakterystyka wykonalności typu 2 „FOCS 1991 i„ Charakterystyka podstawowych wykonalnych funkcjonałów typu skończonego ”STOC 1989.