| rdfs:comment
| - En informatique théorique, plus précisément en théorie de la complexité, P/poly est la classe de problèmes de décision décidés par une famille de circuits booléens de tailles polynomiales. Cette classe a été introduite par Karp et Lipton en 1980. Cette classe est importante, car comme P est incluse dans P/poly, si on démontre que NP ⊈ P/poly, alors on résout le problème ouvert P est différent de NP. (fr)
- In der Komplexitätstheorie ist P/poly die Komplexitätsklasse von Sprachen die von polynomzeit-beschränkten Turing Maschinen mit polynomiell beschränkter erkannt werden. Sie wird auch äquivalent als die Klasse PSIZE von Sprachen definiert, die Schaltkreise polynomieller Größe besitzen. 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. (de)
- En la teoría de la complejidad computacional, P/poly es la clase de complejidad de los lenguajes reconocidos por una máquina de Turing de tiempo polinomial con una función de asesoramiento limitada polinomialmente. También se define de manera equivalente como la clase PSIZE de lenguajes que tienen circuitos de tamaño polinómico. Esto significa que la máquina que reconoce un idioma puede usar una función de asesoramiento diferente o un circuito diferente dependiendo de la longitud de la entrada y que la función o circuito de asesoramiento variará solo según el tamaño 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 é a classe de complexidade das linguagens reconhecidas em tempo polinomial por uma máquina de Turing com um polynomial-bounded advice function. É também equivalentemente definida como a classe PSIZE de linguagens que possuem um circuito de tamanho polinomial. Isso significa que a máquina que reconhece uma linguagem pode usar uma função de aconselhamento diferente ou usar um circuito diferente dependendo do tamanho da entrada,e que a função de aconselhamento ou circuito irá variar apenas em função do tamanho da entrada. (pt)
|
| has abstract
| - In der Komplexitätstheorie ist P/poly die Komplexitätsklasse von Sprachen die von polynomzeit-beschränkten Turing Maschinen mit polynomiell beschränkter erkannt werden. Sie wird auch äquivalent als die Klasse PSIZE von Sprachen definiert, die Schaltkreise polynomieller Größe besitzen. 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. 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. (de)
- En la teoría de la complejidad computacional, P/poly es la clase de complejidad de los lenguajes reconocidos por una máquina de Turing de tiempo polinomial con una función de asesoramiento limitada polinomialmente. También se define de manera equivalente como la clase PSIZE de lenguajes que tienen circuitos de tamaño polinómico. Esto significa que la máquina que reconoce un idioma puede usar una función de asesoramiento diferente o un circuito diferente dependiendo de la longitud de la entrada y que la función o circuito de asesoramiento variará solo según el tamaño 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áximo, n valores de modo que cada número compuesto de n bits se asegure de tener un testigo a en la lista. Por ejemplo, para determinar correctamente la primalidad de los números de 32 bits, es suficiente probar a = 2, 7 y 61. 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ño 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áctica para la computación. 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á limitada por un número relativamente pequeño y las cadenas de consejos son cortas, puede usarse para modelar algoritmos prácticos con una fase de preprocesamiento costosa separada y una fase de procesamiento rápido, como en el ejemplo anterior. (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. For example, the popular Miller–Rabin 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–Rabin example. (en)
- En informatique théorique, plus précisément en théorie de la complexité, P/poly est la classe de problèmes de décision décidés par une famille de circuits booléens de tailles polynomiales. Cette classe a été introduite par Karp et Lipton en 1980. Cette classe est importante, car comme P est incluse dans P/poly, si on démontre que NP ⊈ P/poly, alors on résout le problème ouvert P est différent de NP. (fr)
- Na Teoria da complexidade computacional, P/poly é a classe de complexidade das linguagens reconhecidas em tempo polinomial por uma máquina de Turing com um polynomial-bounded advice function. É também equivalentemente definida como a classe PSIZE de linguagens que possuem um circuito de tamanho polinomial. Isso significa que a máquina que reconhece uma linguagem pode usar uma função de aconselhamento diferente ou usar um circuito diferente dependendo do tamanho da entrada,e que a função de aconselhamento ou circuito irá variar apenas em função do tamanho da entrada. Por exemplo, o popular teste de primalidade Miller-Rabin pode ser formulado como um algoritmo P/polinomial: o "conselho" é uma lista de candidatos de valores para serem testados. É possível pré-computar uma lista de, no máximo, N valores de tal forma que todos os números de n-bits vão ter a certeza de ter uma testemunha a na lista. Por exemplo, se estamos testando um número de 32 bits, é suficiente para testar a = 2, 7 e 61. isso decorre do fato de que para cada n composto, 3/4s de todos os possíveis valores de A são testemunhas; um argumento de contagem simples, semelhante ao da prova de que BPP em P/polinomial abaixo mostra que não existe uma lista adequada de valores para A para cada tamanho de entrada, apesar que encontrá-lo pode ser caro. Note que P/polinomial, ao contrário de outras classes de tempo polinomial, como P ou BPP, não é geralmente considerada uma classe de computação prática. Na verdade, isso contém todas as linguagens unárias "indecidíveis", nenhuma das quais pode ser resolvido geralmente por computadores reais. Por outro lado, se o comprimento de entrada é delimitada por um número relativamente pequeno, e as strings de aconselhamento são curtas, isso pode ser usado para modelar algoritmos práticos, com uma fase cara de pré-processamento separadamente de uma fase de processamento rápido, tal como no exemplo acima. (pt)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)