NP/poli

W teorii złożoności obliczeniowej NP/poly jest klasą złożoności , niejednorodnym odpowiednikiem klasy NP problemów rozwiązywanych w czasie wielomianowym przez niedeterministyczną maszynę Turinga . Jest to niedeterministyczna klasa złożoności odpowiadająca deterministycznej klasie P/poly .

Definicja

NP/poly definiuje się jako klasę problemów, które można rozwiązać w czasie wielomianowym przez niedeterministyczną maszynę Turinga, która ma dostęp do funkcji doradczej ograniczonej wielomianem .

$to$ równoważnie zdefiniować jako klasę problemów taką, że dla każdej instancji $istnieje$ obwód wielomianu rozmiaru w który implementuje weryfikator problemu. $oblicza$$,$$że$ funkcję taką wejście o długości tak dla wtedy i tylko wtedy, gdy istnieje ${\ Displaystyle y}$ dla którego jest prawdziwe ${\ Displaystyle f (x, y)} .$

Aplikacje

NP / poli jest używane w odmianie twierdzenia Mahaneya o nieistnieniu rzadkich języków NP-zupełnych . Samo twierdzenie Mahaneya stwierdza, że ​​​​liczba przypadków tak-o długości $P$ NP-zupełnego nie może być ograniczona wielomianowo, chyba że = NP . Zgodnie z odmianą $,$ liczba przypadków tak musi wynosić co $dla$ dla wielu ${\ displaystyle n}$ , chyba że co-NP jest podzbiorem NP / poly, co (zgodnie z twierdzeniem Karpa – Liptona ) spowodowałoby upadek hierarchii wielomianów . To samo założenie dotyczące twardości obliczeniowej , że co-NP nie jest podzbiorem NP/poly, implikuje również kilka innych wyników w złożoności, takich jak optymalność niektórych technik kernelizacji .