NP/poly

I beräkningskomplexitetsteori är NP/poly en komplexitetsklass , en olikformig analog till klassen NP av problem som kan lösas i polynomtid av en icke-deterministisk Turing- maskin . Det är den icke-deterministiska komplexitetsklassen som motsvarar den deterministiska klassen P/poly .

Definition

NP/poly definieras som klassen av problem som kan lösas i polynomtid av en icke-deterministisk Turing-maskin som har tillgång till en polynom-bunden rådgivningsfunktion .

Det kan på motsvarande sätt definieras som klassen av problem så att det för varje instans storlek $n$ finns en boolesk krets med storlekspolynom i $n$ som implementerar en verifierare för problemet. Det vill säga, kretsen beräknar en funktion $f(x,y)$ så att en ingång $x$ med längden $n$ är en ja-instans för problemet om och bara om det finns $y$ för vilken $f(x,y)$ är sant.

Ansökningar

NP/poly används i en variant av Mahaneys teorem om icke-existensen av glesa NP-kompletta språk. Mahaneys sats säger själv att antalet ja-instanser av längden $n$ av ett NP-komplett problem inte kan vara polynomiellt begränsat om inte P = NP . Enligt varianten måste antalet ja-instanser vara minst $2^{n^{\epsilon }}$ för vissa $\epsilon >0$ och för oändligt många ${ \displaystyle n}$ , om inte co-NP är en delmängd av NP/poly, vilket (genom Karp–Lipton-satsen ) skulle orsaka kollapsen av polynomhierarkin . Samma beräkningshårdhetsantagande att co-NP inte är en delmängd av NP/poly innebär också flera andra resultat i komplexitet, såsom optimaliteten hos vissa kärnbildningstekniker .