P/poly

Dieser Artikel wurde wegen inhaltlicher Mängel auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf mit, die inhaltlichen Mängel dieses Artikels zu beseitigen, und beteilige dich an der Diskussion! (+) Begründung: Es bedarf einer allgemeinverständlichen Einleitung, die zumindest darstellt, worum es geht

In der Komplexitätstheorie ist P/poly die Komplexitätsklasse von Sprachen die von polynomzeit-beschränkten Turing-Maschinen mit polynomiell beschränkter Hinweisfunktion erkannt werden. Sie wird auch äquivalent als die Klasse PSIZE von Sprachen definiert, die Schaltkreise polynomieller Größe besitzen.^[1][2] Dies bedeutet, dass eine Maschine, die eine P/poly Sprache erkennt, je nach Länge der Eingabe eine andere Hinweisfunktion oder eine andere Schaltung verwenden kann und dass die Hinweisfunktion oder Schaltung nur von der Größe der Eingabe abhängt.

Zum Beispiel kann der beliebte Miller-Rabin-Test als P/poly-Algorithmus formuliert werden: Der „Rat“ ist eine Liste von Kandidaten a, die zu testen sind. Es ist möglich, eine Liste mit höchstens n Werten so vorab zu berechnen, dass jede zusammengesetzte n-Bit-Nummer mit Sicherheit einen Zeugen a in der Liste besitzt. Um beispielsweise die Primalität von 32-Bit-Zahlen korrekt zu bestimmen, reicht es aus, a = 2, 7 und 61 zu testen.^[3] Die Existenz von kurzen Listen von Zeugen für Kandidaten folgt aus der Tatsache, dass für jedes zusammengesetzte n 3/4 aller möglichen a-Werte Zeugen sind. Ein einfaches Zählargument ähnlich dem im Beweis unten, dass BPP in P/poly ist, zeigt, dass es für jede Eingabegröße eine geeignete Liste von a-Werten existiert, obwohl es aufwändig sein kann, sie zu finden.

P/poly wird im Gegensatz zu anderen Polynomzeitklassen wie P oder BPP im Allgemeinen nicht als praktische Klasse für Berechnungen angesehen. In der Tat enthält sie jede unentscheidbare unäre Sprache, von der keine im Allgemeinen von realen Computern gelöst werden kann. Wenn andererseits die Eingabelänge durch eine relativ kleine Zahl begrenzt ist und die Hinweiszeichenfolgen kurz sind, können praktische Algorithmen mit einer separaten teuren Vorverarbeitungsphase und einer schnellen Verarbeitungsphase wie im obigen Beispiel modelliert werden.

1. ↑ Referenzfehler: Ungültiges <ref>-Tag; kein Text angegeben für Einzelnachweis mit dem Namen lutz93.
2. ↑ Peter Bro Miltersen: Lecture notes on computational complexity. Archiviert vom Original (nicht mehr online verfügbar) am 23. Februar 2012; abgerufen am 25. Dezember 2009. 
3. ↑ Finding primes & proving primality