| rdfs:comment
| - En théorie de la complexité, un conseil est une entrée supplémentaire passée à une machine de Turing qui dépend de la taille de l'entrée, afin d'aider la machine à reconnaître un langage. Cette notion est introduite par Richard Karp et Richard J. Lipton en 1982. (fr)
- In computational complexity theory, an advice string is an extra input to a Turing machine that is allowed to depend on the length n of the input, but not on the input itself. A decision problem is in the complexity class P/f(n) if there is a polynomial time Turing machine M with the following property: for any n, there is an advice string A of length f(n) such that, for any input x of length n, the machine M correctly decides the problem on the input x, given x and A. Similarly, the class L/poly can be defined as deterministic logspace with a polynomial amount of advice. Known results include: (en)
- En la teoría de la complejidad computacional, una cadena de consejos es una entrada adicional a una máquina de Turing que puede depender de la longitud n de la entrada pero no de la entrada en sí. Un problema de decisión está en la clase de complejidad P/f(n) si hay un tiempo polinómico en la máquina de Turing M con la siguiente propiedad: para cualquier n, hay una cadena de aviso A de longitud f(n) tal que, para cualquier entrada x de longitud n, la máquina M decide correctamente el problema en la entrada x, dados x y A. Los resultados conocidos incluyen: (es)
- Na teoria de complexidade computacional, uma palavra de aviso é uma entrada adicional para uma Máquina de Turing que é permitida depender do comprimento de entrada n, mas não sobre a própria entrada. Um problema de decisão está na classe de complexidade P/f(n) se houver uma Máquina de Turing de tempo polinomial M com a seguinte propriedade: para qualquer n, há uma palavra de aviso A de comprimento f(n), de tal modo que, para qualquer entrada x de comprimento n , a máquina M decidi corretamente o problema da entrada x , dado x e A. Resultados conhecidos incluem:: (pt)
- 在複雜度類裡面, 一個建議字串是一種以原本輸入的長度n來對圖靈機新增加的輸入，並且不是輸入的資料本身。如果存在一個多項式時間圖靈機具有特性如下：對任何自然數n，存在一個建議字串A，長度是f(n)，並且對任何長度是n的輸入x，機器M在給予x和A為輸入的狀態下可以正確判斷x是否在這個問題上正確，我們說這個決定型問題在複雜度類 P/f(n)裡面。 與建議字串有關最常見的複雜度類是，這個複雜度類包含建議字串的長度f(n)屬於任何n的多項式的語言。P/poly等同於以下這個複雜度類：對任何n，均存在一個n的多項式大小的，可以正確決定任何長度為n的輸入。這個等式其中一個方向的推論比較明顯：如果，對任何n，均存在一個多項式大小的布林線路A(n) 可以決定這問題，那我們可以用一個字串代表布林線路，然後圖靈機模擬布林線路的運作。如此一來，則對這問題來說，任何輸入長度為n的話，我們就有一個包含建議字串A(n)的圖靈機可以作正確的決定。等式另一個方向的證明則是先使用了，推論出我們可以用一個多項式時間的布林線路來模擬一個多項式時間的圖靈機。然後我們注意到，模擬一個有建議字串的圖靈機並不比模擬一個普通的圖靈機來得更難，因為我們可以將建議字串整個包含在線路裡面(因為建議字串是n的多項式大小)。這樣的話，這個方向的等式也成立了。 相同的，我們可以定義出為有多項式長度建議字串的決定型對數空間。 (zh)
|
| has abstract
| - In computational complexity theory, an advice string is an extra input to a Turing machine that is allowed to depend on the length n of the input, but not on the input itself. A decision problem is in the complexity class P/f(n) if there is a polynomial time Turing machine M with the following property: for any n, there is an advice string A of length f(n) such that, for any input x of length n, the machine M correctly decides the problem on the input x, given x and A. The most common complexity class involving advice is P/poly where advice length f(n) can be any polynomial in n. P/poly is equal to the class of decision problems such that, for every n, there exists a polynomial size Boolean circuit correctly deciding the problem on all inputs of length n. One direction of the equivalence is easy to see. If, for every n, there is a polynomial size Boolean circuit A(n) deciding the problem, we can use a Turing machine that interprets the advice string as a description of the circuit. Then, given the description of A(n) as the advice, the machine will correctly decide the problem on all inputs of length n. The other direction uses a simulation of a polynomial-time Turing machine by a polynomial-size circuit as in one proof of Cook's theorem. Simulating a Turing machine with advice is no more complicated than simulating an ordinary machine, since the advice string can be incorporated into the circuit. Because of this equivalence, P/poly is sometimes defined as the class of decision problems solvable by polynomial size Boolean circuits, or by polynomial-size non-uniform Boolean circuits. P/poly contains both P and BPP (Adleman's theorem). It also contains some undecidable problems, such as the unary version of every undecidable problem, including the halting problem. Because of that, it is not contained in DTIME (f(n)) or NTIME (f(n)) for any f. Advice classes can be defined for other resource bounds instead of P. For example, taking a non-deterministic polynomial time Turing machine with an advice of length f(n) gives the complexity class NP/f(n). If we are allowed an advice of length 2n, we can use it to encode whether each input of length n is contained in the language. Therefore, any boolean function is computable with an advice of length 2n and advice of more than exponential length is not meaningful. Similarly, the class L/poly can be defined as deterministic logspace with a polynomial amount of advice. Known results include:
* The classes NL/poly and UL/poly are the same, i.e. nondeterministic logarithmic space computation with advice can be made unambiguous. This may be proved using an isolation lemma.
* It is known that coNEXP is contained in NEXP/poly.
* If NP is contained in P/poly, then the polynomial time hierarchy collapses (Karp-Lipton theorem). (en)
- En la teoría de la complejidad computacional, una cadena de consejos es una entrada adicional a una máquina de Turing que puede depender de la longitud n de la entrada pero no de la entrada en sí. Un problema de decisión está en la clase de complejidad P/f(n) si hay un tiempo polinómico en la máquina de Turing M con la siguiente propiedad: para cualquier n, hay una cadena de aviso A de longitud f(n) tal que, para cualquier entrada x de longitud n, la máquina M decide correctamente el problema en la entrada x, dados x y A. La clase de complejidad más común que implica asesoramiento es donde la longitud de asesoramiento/consejo f(n) puede ser cualquier polinomio en n. P/poly es igual a la clase de problemas de decisión de modo que, para cada n, existe un de tamaño polinómico que decide correctamente el problema en todas las entradas de longitud n. Una de las direcciones de la equivalencia es fácil de ver: si, por cada n, hay un circuito booleano A(n) de tamaño polinómico que decide el problema, podemos usar una máquina de Turing que interpreta la cadena de consejos como una descripción del circuito. Luego, dada la descripción de A(n) como consejo, la máquina decidirá correctamente el problema en todas las entradas de longitud n. La otra dirección usa una simulación de una máquina de Turing de tiempo polinómico mediante un circuito de tamaño polinómico como en una prueba del Teorema de Cook. Simular una máquina de Turing con consejos no es más complicado que simular una máquina ordinaria, ya que la cadena de consejos se puede incorporar al circuito. Debido a esta equivalencia, P/poly a veces se define como la clase de problemas de decisión que se pueden resolver mediante circuitos booleanos de tamaño polinómico o mediante circuitos booleanos . P/poly contiene P y (teorema de Adleman). También contiene algunos problemas indecidibles, como la versión unaria de cada problema indecidible, incluido el problema de la parada. Debido a eso, no está contenido en DTIME(f(n)) o NTIME(f(n)) para ninguna f. Las clases de consejos se pueden definir para otros límites de recursos en lugar de P. Por ejemplo, tomar una máquina de Turing de tiempo polinomial no determinista con un consejo de longitud f(n) da la clase de complejidad NP/f(n). Si se nos permite un consejo de longitud 2n, podemos usarlo para codificar si cada entrada de longitud n está contenida en el lenguaje. Por lo tanto, cualquier función booleana es computable con un consejo de longitud 2n y un consejo de longitud más que exponencial no es significativo. De manera similar, la clase se puede definir como espacio de registro determinista con una cantidad polinómica de consejos. Los resultados conocidos incluyen:
* Las clases NL/poly y UL/poly son las mismas, es decir, el cálculo del espacio logarítmico no determinista con asesoramiento puede hacerse inequívoco. Esto se puede probar usando un .
* Se sabe que coNEXP está contenido en NEXP/poly.
* Si NP está contenido en P/poly, entonces la jerarquía de tiempo polinómica se colapsa. (es)
- En théorie de la complexité, un conseil est une entrée supplémentaire passée à une machine de Turing qui dépend de la taille de l'entrée, afin d'aider la machine à reconnaître un langage. Cette notion est introduite par Richard Karp et Richard J. Lipton en 1982. (fr)
- Na teoria de complexidade computacional, uma palavra de aviso é uma entrada adicional para uma Máquina de Turing que é permitida depender do comprimento de entrada n, mas não sobre a própria entrada. Um problema de decisão está na classe de complexidade P/f(n) se houver uma Máquina de Turing de tempo polinomial M com a seguinte propriedade: para qualquer n, há uma palavra de aviso A de comprimento f(n), de tal modo que, para qualquer entrada x de comprimento n , a máquina M decidi corretamente o problema da entrada x , dado x e A. A classe de complexidade mais comum envolvendo aviso é P/polinomial onde o comprimento do aviso f(n) pode ser qualquer polinômio em n. P/polinomial é igual ao problema de decisão de classes de tal modo que, para todo n, existe um Circuito booleano de tamanho polinomial decidindo corretamente o problema em todas as entradas de comprimento n. Uma direção da equivalência é fácil de ver. Se, para cada n, existe um circuito booleano de tamanho polinomial A(n) decidindo o problema, podemos usar uma Máquina de Turing que interpreta a palavra de aviso como uma descrição do circuito. Então, dada a descrição de A(n) como o aviso, a máquina vai decidir corretamente o problema em todas as entradas de comprimento n. A outra direção utiliza uma simulação de uma máquina de Turing de tempo polinomial por um circuito de tamanho polinomial como em uma prova do Teorema de Cook-Levin. Simulando uma máquina de Turing com avisos não é mais complicado do que simulando uma máquina normal, uma vez que a palavra de aviso pode ser incorporada no circuito. Devido a esta equivalência, P/polinomial às vezes é definida como a classe de problemas de decisão que podem ser resolvidos por circuitos booleanos de tamanho polinomiais, ou por um circuito booleano de tamanho polinomial não uniforme. P/polinomial contém P e BPP (teorema de Adleman). Ele também contém alguns problemas indecidíveis, tais como a versão unary de cada problema indecidível, incluindo o Problema da parada. Por causa disso, não está contido no DTIME (f(n)) ou NTIME (f(n)) para qualquer f. Classes de aviso podem ser definidas para outros limites de recursos ao invés de P. Por exemplo, tomando uma máquina de Turing não-determinística de tempo polinomial com um aviso de comprimento f(n) dá a classe de complexidade NP/f(n). Se nos é permitido um aviso de comprimento 2n, podemos usá-lo para codificar se cada entrada de comprimento n está contido na linguagem. Portanto, qualquer função booleana é computável com um aviso de comprimento 2n e aviso de tamanho maior que exponencial não é significativo Similarmente, a classe L/polinomial pode ser definida como LSPACE com um aviso de valor polinomial. Resultados conhecidos incluem::
* As classes NL/polinomial e UL/polinomial são as mesmas, exemplo, computação de espaço logarítimico não deterministico com aviso pode ser feita sem ambiguidades. Esse meio pode ser provado usando o lemma de isolamento.
* Sabe-se que coNEXP está contido em NEXP/poly. (pt)
- 在複雜度類裡面, 一個建議字串是一種以原本輸入的長度n來對圖靈機新增加的輸入，並且不是輸入的資料本身。如果存在一個多項式時間圖靈機具有特性如下：對任何自然數n，存在一個建議字串A，長度是f(n)，並且對任何長度是n的輸入x，機器M在給予x和A為輸入的狀態下可以正確判斷x是否在這個問題上正確，我們說這個決定型問題在複雜度類 P/f(n)裡面。 與建議字串有關最常見的複雜度類是，這個複雜度類包含建議字串的長度f(n)屬於任何n的多項式的語言。P/poly等同於以下這個複雜度類：對任何n，均存在一個n的多項式大小的，可以正確決定任何長度為n的輸入。這個等式其中一個方向的推論比較明顯：如果，對任何n，均存在一個多項式大小的布林線路A(n) 可以決定這問題，那我們可以用一個字串代表布林線路，然後圖靈機模擬布林線路的運作。如此一來，則對這問題來說，任何輸入長度為n的話，我們就有一個包含建議字串A(n)的圖靈機可以作正確的決定。等式另一個方向的證明則是先使用了，推論出我們可以用一個多項式時間的布林線路來模擬一個多項式時間的圖靈機。然後我們注意到，模擬一個有建議字串的圖靈機並不比模擬一個普通的圖靈機來得更難，因為我們可以將建議字串整個包含在線路裡面(因為建議字串是n的多項式大小)。這樣的話，這個方向的等式也成立了。 因為這個恆等式的關係，P/poly有時候我們以以能夠被多項式大小布林線路決定的題目來定義，或者是能被多項式大小布林線路解決的線路。 P/poly包含了P和BPP。它也包含了一些 不可決定的問題，例如說一些不可決定語言的一元版本，包含了停機問題。因此，對任何f(n)，P/poly不包含在DTIME (f(n))或者NTIME (f(n))裡面。 不只有P可以被用來增加建議字串變成新的複雜度類。舉例說來，我們可以將具有長度為f(n)建議字串的多項式時間圖靈機定義為複雜度類NP/f(n)。 如果我們允許2n這麼長的建議字串，那我們就可以把n這個長度的所有可能輸入值跟對應的答案都寫入這個建議字串內。因此，我們知道任何函式在建議字串長度為2n的條件下一定是可以計算的，所以超過指數長度的建議字串是沒有意義的。 相同的，我們可以定義出為有多項式長度建議字串的決定型對數空間。 (zh)
|
![[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)