. . "In computational complexity theory, P/poly is a complexity class representing problems that can be solved by small circuits. More precisely, it is the set of formal languages that have polynomial-size circuit families. It can also be defined equivalently in terms of Turing machines with advice, extra information supplied to the Turing machine along with its input, that may depend on the input length but not on the input itself. In this formulation, P/poly is the class of decision problems that can be solved by a polynomial-time Turing machine with advice strings of length polynomial in the input size. These two different definitions make P/poly central to circuit complexity and non-uniform complexity. For example, the popular Miller\u2013Rabin primality test can be formulated as a P/poly algorithm: the \"advice\" is a list of candidate values to test. It is possible to precompute a list of values such that every composite -bit number will be certain to have a witness in the list. For example, to correctly determine the primality of 32-bit numbers, it is enough to test . The existence of short lists of candidate witnesses follows from the fact that for each composite , three out of four candidate values successfully detect that is composite. From this, a simple counting argument similar to the one in the proof that BPP P/poly below shows that there exists a suitable list of candidate values for every input size, and more strongly that most long-enough lists of candidate values will work correctly, although finding a list that is guaranteed to work may be expensive. P/poly, unlike other polynomial-time classes such as P or BPP, is not generally considered a practical class for computing. Indeed, it contains every undecidable unary language, none of which can be solved in general by real computers. On the other hand, if the input length is bounded by a relatively small number and the advice strings are short, it can be used to model practical algorithms with a separate expensive preprocessing phase and a fast processing phase, as in the Miller\u2013Rabin example."@en . . . "P/poly"@fr . . . "P/poly"@en . . . . "14026"^^ . . "2052415"^^ . . . . "P/poly"@de . . . "1115546296"^^ . . . . . . . . "In der Komplexit\u00E4tstheorie ist P/poly die Komplexit\u00E4tsklasse von Sprachen die von polynomzeit-beschr\u00E4nkten Turing Maschinen mit polynomiell beschr\u00E4nkter erkannt werden. Sie wird auch \u00E4quivalent als die Klasse PSIZE von Sprachen definiert, die Schaltkreise polynomieller Gr\u00F6\u00DFe besitzen. Dies bedeutet, dass eine Maschine, die eine P/poly Sprache erkennt, je nach L\u00E4nge der Eingabe eine andere Hinweisfunktion oder eine andere Schaltung verwenden kann und dass die Hinweisfunktion oder Schaltung nur von der Gr\u00F6\u00DFe der Eingabe abh\u00E4ngt."@de . . . . . "P/poly"@es . "In der Komplexit\u00E4tstheorie ist P/poly die Komplexit\u00E4tsklasse von Sprachen die von polynomzeit-beschr\u00E4nkten Turing Maschinen mit polynomiell beschr\u00E4nkter erkannt werden. Sie wird auch \u00E4quivalent als die Klasse PSIZE von Sprachen definiert, die Schaltkreise polynomieller Gr\u00F6\u00DFe besitzen. Dies bedeutet, dass eine Maschine, die eine P/poly Sprache erkennt, je nach L\u00E4nge der Eingabe eine andere Hinweisfunktion oder eine andere Schaltung verwenden kann und dass die Hinweisfunktion oder Schaltung nur von der Gr\u00F6\u00DFe der Eingabe abh\u00E4ngt. 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\u00F6glich, eine Liste mit h\u00F6chstens 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\u00E4t von 32-Bit-Zahlen korrekt zu bestimmen, reicht es aus, a = 2, 7 und 61 zu testen. Die Existenz von kurzen Listen von Zeugen f\u00FCr Kandidaten folgt aus der Tatsache, dass f\u00FCr jedes zusammengesetzte n 3/4 aller m\u00F6glichen a-Werte Zeugen sind. Ein einfaches Z\u00E4hlargument \u00E4hnlich dem im Beweis unten, dass BPP in P/poly ist, zeigt, dass es f\u00FCr jede Eingabegr\u00F6\u00DFe eine geeignete Liste von a-Werten existiert, obwohl es aufw\u00E4ndig sein kann, sie zu finden. P/poly wird im Gegensatz zu anderen Polynomzeitklassen wie P oder BPP im Allgemeinen nicht als praktische Klasse f\u00FCr Berechnungen angesehen. In der Tat enth\u00E4lt sie jede unentscheidbare un\u00E4re Sprache, von der keine im Allgemeinen von realen Computern gel\u00F6st werden kann. Wenn andererseits die Eingabel\u00E4nge durch eine relativ kleine Zahl begrenzt ist und die Hinweiszeichenfolgen kurz sind, k\u00F6nnen praktische Algorithmen mit einer separaten teuren Vorverarbeitungsphase und einer schnellen Verarbeitungsphase wie im obigen Beispiel modelliert werden."@de . . . . "En la teor\u00EDa de la complejidad computacional, P/poly es la clase de complejidad de los lenguajes reconocidos por una m\u00E1quina de Turing de tiempo polinomial con una funci\u00F3n de asesoramiento limitada polinomialmente. Tambi\u00E9n se define de manera equivalente como la clase PSIZE de lenguajes que tienen circuitos de tama\u00F1o polin\u00F3mico.\u200B\u200B Esto significa que la m\u00E1quina que reconoce un idioma puede usar una funci\u00F3n de asesoramiento diferente o un circuito diferente dependiendo de la longitud de la entrada y que la funci\u00F3n o circuito de asesoramiento variar\u00E1 solo seg\u00FAn el tama\u00F1o de la entrada. Por ejemplo, la popular prueba de primalidad Miller-Rabin puede formularse como un algoritmo P/poly: el \"consejo\" es una lista de candidatos a valores para probar. Es posible calcular previamente una lista de, como m\u00E1ximo, n valores de modo que cada n\u00FAmero compuesto de n bits se asegure de tener un testigo a en la lista. Por ejemplo, para determinar correctamente la primalidad de los n\u00FAmeros de 32 bits, es suficiente probar a = 2, 7 y 61.\u200B La existencia de listas cortas de testigos candidatos sigue del hecho de que para cada n compuesto, 3/4s de todos los valores posibles son testigos; un simple argumento de recuento similar a la de la prueba de que BPP en P/poly muestra que existe una lista adecuada de valores a para cada tama\u00F1o de entrada, aunque encontrarla puede ser caro. P/poly, a diferencia de otras clases de tiempo polinomial como P o , generalmente no se considera una clase pr\u00E1ctica para la computaci\u00F3n. De hecho, contiene todos los indecidibles, ninguno de los cuales puede ser resuelto en general por computadoras reales. Por otro lado, si la longitud de entrada est\u00E1 limitada por un n\u00FAmero relativamente peque\u00F1o y las cadenas de consejos son cortas, puede usarse para modelar algoritmos pr\u00E1cticos con una fase de preprocesamiento costosa separada y una fase de procesamiento r\u00E1pido, como en el ejemplo anterior."@es . . . . "P/polinomial"@pt . . "Na Teoria da complexidade computacional, P/poly \u00E9 a classe de complexidade das linguagens reconhecidas em tempo polinomial por uma m\u00E1quina de Turing com um polynomial-bounded advice function. \u00C9 tamb\u00E9m equivalentemente definida como a classe PSIZE de linguagens que possuem um circuito de tamanho polinomial. Isso significa que a m\u00E1quina que reconhece uma linguagem pode usar uma fun\u00E7\u00E3o de aconselhamento diferente ou usar um circuito diferente dependendo do tamanho da entrada,e que a fun\u00E7\u00E3o de aconselhamento ou circuito ir\u00E1 variar apenas em fun\u00E7\u00E3o do tamanho da entrada."@pt . . . . . . . . . . "En la teor\u00EDa de la complejidad computacional, P/poly es la clase de complejidad de los lenguajes reconocidos por una m\u00E1quina de Turing de tiempo polinomial con una funci\u00F3n de asesoramiento limitada polinomialmente. Tambi\u00E9n se define de manera equivalente como la clase PSIZE de lenguajes que tienen circuitos de tama\u00F1o polin\u00F3mico.\u200B\u200B Esto significa que la m\u00E1quina que reconoce un idioma puede usar una funci\u00F3n de asesoramiento diferente o un circuito diferente dependiendo de la longitud de la entrada y que la funci\u00F3n o circuito de asesoramiento variar\u00E1 solo seg\u00FAn el tama\u00F1o de la entrada."@es . . . "In computational complexity theory, P/poly is a complexity class representing problems that can be solved by small circuits. More precisely, it is the set of formal languages that have polynomial-size circuit families. It can also be defined equivalently in terms of Turing machines with advice, extra information supplied to the Turing machine along with its input, that may depend on the input length but not on the input itself. In this formulation, P/poly is the class of decision problems that can be solved by a polynomial-time Turing machine with advice strings of length polynomial in the input size. These two different definitions make P/poly central to circuit complexity and non-uniform complexity."@en . . . . . . . . . . . . . "Na Teoria da complexidade computacional, P/poly \u00E9 a classe de complexidade das linguagens reconhecidas em tempo polinomial por uma m\u00E1quina de Turing com um polynomial-bounded advice function. \u00C9 tamb\u00E9m equivalentemente definida como a classe PSIZE de linguagens que possuem um circuito de tamanho polinomial. Isso significa que a m\u00E1quina que reconhece uma linguagem pode usar uma fun\u00E7\u00E3o de aconselhamento diferente ou usar um circuito diferente dependendo do tamanho da entrada,e que a fun\u00E7\u00E3o de aconselhamento ou circuito ir\u00E1 variar apenas em fun\u00E7\u00E3o do tamanho da entrada. Por exemplo, o popular teste de primalidade Miller-Rabin pode ser formulado como um algoritmo P/polinomial: o \"conselho\" \u00E9 uma lista de candidatos de valores para serem testados. \u00C9 poss\u00EDvel pr\u00E9-computar uma lista de, no m\u00E1ximo, N valores de tal forma que todos os n\u00FAmeros de n-bits v\u00E3o ter a certeza de ter uma testemunha a na lista. Por exemplo, se estamos testando um n\u00FAmero de 32 bits, \u00E9 suficiente para testar a = 2, 7 e 61. isso decorre do fato de que para cada n composto, 3/4s de todos os poss\u00EDveis valores de A s\u00E3o testemunhas; um argumento de contagem simples, semelhante ao da prova de que BPP em P/polinomial abaixo mostra que n\u00E3o existe uma lista adequada de valores para A para cada tamanho de entrada, apesar que encontr\u00E1-lo pode ser caro. Note que P/polinomial, ao contr\u00E1rio de outras classes de tempo polinomial, como P ou BPP, n\u00E3o \u00E9 geralmente considerada uma classe de computa\u00E7\u00E3o pr\u00E1tica. Na verdade, isso cont\u00E9m todas as linguagens un\u00E1rias \"indecid\u00EDveis\", nenhuma das quais pode ser resolvido geralmente por computadores reais. Por outro lado, se o comprimento de entrada \u00E9 delimitada por um n\u00FAmero relativamente pequeno, e as strings de aconselhamento s\u00E3o curtas, isso pode ser usado para modelar algoritmos pr\u00E1ticos, com uma fase cara de pr\u00E9-processamento separadamente de uma fase de processamento r\u00E1pido, tal como no exemplo acima."@pt . . . "En informatique th\u00E9orique, plus pr\u00E9cis\u00E9ment en th\u00E9orie de la complexit\u00E9, P/poly est la classe de probl\u00E8mes de d\u00E9cision d\u00E9cid\u00E9s par une famille de circuits bool\u00E9ens de tailles polynomiales. Cette classe a \u00E9t\u00E9 introduite par Karp et Lipton en 1980. Cette classe est importante, car comme P est incluse dans P/poly, si on d\u00E9montre que NP \u2288 P/poly, alors on r\u00E9sout le probl\u00E8me ouvert P est diff\u00E9rent de NP."@fr . "En informatique th\u00E9orique, plus pr\u00E9cis\u00E9ment en th\u00E9orie de la complexit\u00E9, P/poly est la classe de probl\u00E8mes de d\u00E9cision d\u00E9cid\u00E9s par une famille de circuits bool\u00E9ens de tailles polynomiales. Cette classe a \u00E9t\u00E9 introduite par Karp et Lipton en 1980. Cette classe est importante, car comme P est incluse dans P/poly, si on d\u00E9montre que NP \u2288 P/poly, alors on r\u00E9sout le probl\u00E8me ouvert P est diff\u00E9rent de NP."@fr . .