a primeira coisa A entender é que a P e NP classificar as línguas, e não problemas. Para entender o que isso significa, Precisamos de algumas outras definições primeiro.
um alfabeto é um conjunto finito não-vazio de símbolos.
{01} é um alfabeto como é o conjunto de caracteres ASCII. {} não é um alfabeto porque está vazio. N (os inteiros) não é um alfabeto porque não é finito.
Let Σ be an alphabet. Uma concatenação ordenada de um número finito de símbolos de Σ é chamada de palavra sobre Σ.
string 101 é uma palavra sobre o alfabeto {01}. A palavra vazia (muitas vezes escrita Como ε) é uma palavra sobre qualquer alfabeto. A string penguin é uma palavra sobre o alfabeto contendo os caracteres ASCII. A notação decimal do número π não é uma palavra sobre o alfabeto {.0123456789} porque ele não é finito.
o comprimento de uma palavra w, escrita como| w/, é o número de símbolos nela.
Por exemplo, |hello| = 5 e |ε| = 0. For any word w | / w / ∈ n and therefore finite.
Let Σ be an alphabet. O conjunto Σ＊ contém todas as palavras sobre Σ, incluindo ε. O conjunto Σ+ contém todas as palavras sobre Σ, excluindo ε. Para n ∈ n, Σn é o conjunto de palavras de comprimento n.
para cada alfabeto Σ, Σ and E Σ+ São conjuntos contáveis infinitos. Para o conjunto de caracteres ASCII ΣASCII, as expressões regulares .* e .+ denotar ΣASCII＊ e ΣASCII+, respectivamente.
{01}7 é o conjunto de ASCII de 7 bits códigos {00000000000001111111101}32 é o conjunto de valores inteiros de 32 bits.
Let Σ be an alphabet and L⊆ Σ＊. L é chamada de uma língua Sobre Σ.
para um alfabeto Σ, o conjunto vazio e Σ＊ São linguagens triviais sobre Σ. O primeiro é muitas vezes referido como a língua vazia. A língua vazia {} e a língua que contém apenas a palavra vazia {ε} são diferentes.
O subconjunto de {01}32 que corresponde a valores de ponto flutuante não NaN IEEE 754 é uma linguagem finita.
As linguagens podem ter um número infinito de palavras, mas cada linguagem é contável. The set of strings {12, …} denoting the integers in decimal notation is an infinite language over the alphabet {0123456789}. O conjunto infinito de seqüências {23571113, …} denota o primeiro-números em notação decimal é um bom subconjunto delas. A linguagem que contém todas as palavras que correspondem à expressão regular ?\d+\.\d*(?\d+)? é uma linguagem sobre o conjunto de caracteres ASCII (que denota um subconjunto das expressões de ponto flutuante válidas definidas pela linguagem de programação C).
não há nenhuma linguagem contendo todos os números reais (em qualquer notação) porque o conjunto de números reais não é contável.
Let Σ be an alphabet and L⊆ Σ＊. Uma máquina d decide L se para cada entrada w ∈ Σ＊ ele calcula a função característica xL(w) em tempo finito. A função característica é definida como
χL: Σ＊ → {0, 1} w ↦ 1, w ∈ L 0, otherwise.tal máquina é chamada de decider para L. nós escrevemos “D(w) = x” Para “dado w, D Saídas x”.
Existem muitos modelos de máquinas. O mais geral que está em uso prático hoje é o modelo de uma máquina de Turing. Uma máquina de Turing tem armazenamento linear ilimitado agrupado em células. Cada célula pode conter exatamente um símbolo de um alfabeto em qualquer ponto do tempo. A máquina de Turing executa sua computação como uma sequência de passos de computação. Em cada passo, ele pode ler uma célula, possivelmente sobrepor o seu valor e mover a cabeça de leitura/escrita por uma posição para a esquerda ou direita. A ação que a máquina irá executar é controlada por um autômato de estado finito.
uma máquina de acesso aleatório com um conjunto finito de instruções e armazenamento ilimitado é outro modelo de máquina que é tão poderoso quanto o modelo da Máquina de Turing.
para o bem desta discussão, não nos incomodaremos com o modelo de máquina preciso que usamos, mas sim suficiente para dizer que a máquina tem uma unidade de controle determinístico finita, armazenamento ilimitado e realiza uma computação como uma sequência de passos que podem ser contados.uma vez que o usou na sua pergunta, presumo que já esteja familiarizado com a notação “big-O”, por isso, aqui está apenas uma actualização rápida.
Let f: n → be a function. O conjunto S(f) contém todas as funções g: N → N para os quais existem constantes n0 ∈ N e c ∈ N tal que para cada n ∈ N, com n > n0 é verdade que g(n) ≤ c f(n).
Agora estamos preparados para abordar a questão real.
A classe de P contém todas as linguagens L para as quais existe uma máquina de Turing D que decide L e uma constante k ∈ N tal que, para cada entrada w, D pára após, no máximo, T(|w|) passos para uma função T ∈ O(n ↦ nk).
Since O( n ↦ nk), while mathematically correct, is inconvenient to write and read, most people – to be honest, everybody except myself – usually writes simply O(nk).
Note que o limite depende do comprimento de w. Portanto, o argumento de que a linguagem dos números primos é apenas correto para números em unaray codificações, onde para a codificação w de um número n, o comprimento da codificação |w| é proporcional a n. Ninguém jamais iria usar tal codificação na prática. Usando um algoritmo mais avançado do que simplesmente tentando todos os fatores possíveis, pode ser mostrado, no entanto, que a linguagem dos números primos permanece em P se as entradas são codificadas em binário (ou para qualquer outra base). (Apesar do grande interesse, isso só poderia ser provado por Manindra Agrawal, Neeraj Kayal, e Nitin Saxena em um papel premiado em 2004 para que você possa adivinhar que o algoritmo não é muito simples.)
as linguagens triviais {} e Σ and e a linguagem não trivial {ε} estão obviamente em P (para qualquer alfabeto Σ). Você pode escrever funções em sua linguagem de programação favorita que tomam uma cadeia de caracteres como entrada e retornam um booleano dizendo se a cadeia é uma palavra da linguagem para cada um destes e provar que sua função tem complexidade polinomial de tempo de execução?
Cada linguagem regular (uma linguagem descrita por uma expressão regular) em P.
Deixe Σ ser um alfabeto e L ⊆ Σ＊. Uma máquina V que toma uma tupla codificada de duas palavras w, c ∈ Σ Σ e Saídas 0 ou 1 após um número finito de passos é um verificador para L se ele tem as seguintes propriedades.
- Given (w, c), V outputs 1 only if w ∈ L.
- Para cada W, L, there exists a c Σ Σ such such that V(w, c) = 1.
O c na definição acima é chamado de testemunha (ou certificado).
um verificador é permitido dar falsos negativos para a testemunha errada, mesmo se w realmente está em L. não é, no entanto, permitido dar falsos positivos. Também é necessário que para cada palavra na língua, exista pelo menos uma testemunha.
para a linguagem composta, que contém as codificações decimais de todos os inteiros que não são primos, uma testemunha pode ser uma fatoração. Por exemplo, (659, 709)é uma testemunha para467231 COMPOSITE composto. Você pode facilmente verificar que em uma folha de papel enquanto sem a testemunha dada, provando que 467231 não é primo seria difícil sem usar um computador.não dissemos nada sobre como uma testemunha apropriada pode ser encontrada. Esta é a parte não-determinística.
A classe NP contém todas as linguagens L para as quais existe uma máquina de Turing V, que verifica a L e uma constante k ∈ N tal que, para cada entrada (w, c), V pára após, no máximo, T(|w|) passos para uma função T ∈ O(n ↦ nk).
Note que a definição acima implica que, para cada w ∈ L existe uma testemunha c com |c| ≤ T(|w|). (A máquina de Turing não pode olhar para mais símbolos da testemunha.)
NP is a superset of P (why?). Não se sabe se existem línguas que estão em NP, mas não em P.
fatoração inteira não é uma linguagem per se. No entanto, podemos construir uma linguagem que representa o problema de decisão associado a ela. Isto é, uma linguagem que contém todas as tuplas (n, m) tal que n tem um fator d com d ≤ m. Vamos chamar este fator de linguagem. Se você tem um algoritmo para decidir o fator, Ele pode ser usado para computar uma fatoração completa com apenas sobrecarga polinomial, realizando uma pesquisa binária recursiva para cada fator primo.
é fácil mostrar que o fator está em NP. Uma testemunha apropriada seria simplesmente o fator d em si e tudo o verificador teria que fazer é verificar que d ≤ m E N mod d = 0. Tudo isso pode ser feito em tempo polinomial. (Lembre-se, novamente, que é o comprimento da codificação que conta e que é logarítmica em n.)
Se você pode mostrar que a FACTOR é também em P, você pode ter certeza de obter muitos cool awards. (E você quebrou uma parte significativa da criptografia de hoje.)
para cada linguagem em NP, há um algoritmo de Força bruta que decide deterministicamente. Ele simplesmente realiza uma busca exaustiva sobre todas as testemunhas. (Note que o comprimento máximo de uma testemunha é limitado por um polinômio. Então, seu algoritmo para decidir números primos era na verdade um algoritmo de Força bruta para decidir composto.
para abordar a sua pergunta final, precisamos introduzir a redução. As reduções são um conceito muito poderoso da ciência da Computação Teórica. Reduzir um problema para outro significa basicamente resolver um problema através da resolução de outro problema.
Let Σ be an alphabet and a And B be languages over Σ. A é polinomial-time muitos-um redutível a B Se existe uma função f: Σ → → Σ with com as seguintes propriedades.
- w w A A f(w) ∈ B para todos W Σ Σ Σ.
- A função f pode ser computada por uma máquina de Turing para cada entrada w em um número de passos limitada por um polinômio em |w|.
neste caso, escrevemos a ≤p B.
por exemplo, seja A linguagem que contém todos os grafos (codificados como matriz de adjacência) que contêm um triângulo. (Um triângulo é um ciclo de comprimento 3.) Let further B be the language that contains all matrices with non-zero trace. (The trace of a matrix is the sum of its main diagonal elements.) Then a is polynomial-time many-one reducible to B. To prove this, we need to find an appropriate transformation function F. In this case, we can set f to compute the 3rd power of the adjacency matrix. Isso requer dois produtos de matriz, cada um dos quais tem complexidade polinomial.é trivialmente verdade que L ≤P L. (pode prová-lo formalmente?)
vamos aplicar isto a NP agora.
a language L is NP-hard if and only if L ‘≤P L for every language l ‘ ∈ NP.
uma língua NP-dura pode ou não estar na própria NP.
a language L is NP-complete if and only if
- L ∈ NP and
- L is NP-hard.
a mais famosa linguagem NP-completa é SAT. Contém todas as fórmulas booleanas que podem ser satisfeitas. Por exemplo, (a ∨ b) ∧ (A ∨ b) SAT SAT. Uma testemunha válida é {a = 1, b = 0}. A fórmula (A ∨ b) ∧ (A ∨ b)) b SAT SAT. (Como você provaria isso?)
não é difícil mostrar que SAT ∈ NP. Para mostrar a NP-dureza do SAT é algum trabalho, mas foi feito em 1971 por Stephen Cook.
Uma vez que uma linguagem NP-completa era conhecida, era relativamente simples mostrar a NP-completude de outras linguagens através da redução. Se a linguagem A é conhecida como NP-hard, então mostrando que a ≤p B mostra que B é NP-hard, também (via a transitividade de “≤p”). Em 1972 Richard Karp publicou uma lista de 21 línguas que ele poderia mostrar eram NP-completo via redução (transitiva) do SAT. (Este é o único artigo nesta resposta que eu realmente recomendo que você leia. Ao contrário dos outros, não é difícil de entender e dá uma idéia muito boa de como provar NP-completude via redução funciona.)
finalmente, um breve resumo. Usaremos os símbolos NPH e NPC para denotar as classes de NP-hard e NP-completas, respectivamente.
- P ⊆ NP
- NPC &subconjunto; NP e NPC &subconjunto; NPH, na verdade NPC = NP ∩ NPH por definição
- (A ∈ NP) ∧ B ∈ NPH) ⇒ A ≤p B
Observe que a inclusão NPC &subconjunto; NP é devida mesmo no caso em que P = NP. Para ver isso, deixe claro que nenhuma linguagem não trivial pode ser reduzida a uma linguagem trivial e existem linguagens triviais em P, bem como linguagens não triviais em NP. Este é um caso de Canto (não muito interessante), no entanto.
Sua fonte primária de confusão parece ser que você estava pensando no “n” Em “O(N ↦ f(n))” Como a interpretação da entrada de um algoritmo quando ele realmente se refere ao comprimento da entrada. Esta é uma distinção importante porque significa que a complexidade assintótica de um algoritmo depende da codificação usada para a entrada.
Esta semana, um novo recorde para o maior primo conhecido de Mersenne foi alcançado. O maior número primo actualmente conhecido é 274 207 281 − 1. Este número é tão grande que me dá uma dor de cabeça então eu vou usar um menor no seguinte exemplo: 231 – 1 = 2 147 483 647. Pode ser codificado de formas diferentes.
- por sua Mersenne expoente como um número decimal:
31(2 bytes) - como número decimal:
2147483647(10 bytes) - como unário número:
11111…11onde…deverá ser substituída por 2 147 483 640 mais1s (quase 2 GiB)
Todas essas cadeias de codificar o mesmo número e dada qualquer destes, podemos facilmente construir qualquer outra codificação do mesmo número. (Poderá substituir a codificação decimal por binário, octal ou hexadecimal, se quiser. Ele só muda o comprimento por um fator constante.)
O algoritmo ingênuo para testar a primalidade é apenas polinomial para codificações unárias. O teste de primalidade AKS é polinomial para decimal (ou qualquer outra base b ≥ 2). O teste de primalidade Lucas-Lehmer é o algoritmo mais conhecido para o p primes MP de Mersenne com um primo ímpar, mas ainda é exponencial no comprimento da codificação binária do expoente p de Mersenne (polinomial em p).
Se queremos falar sobre a complexidade de um algoritmo, é muito importante que sejamos muito claros sobre a representação que usamos. Em geral, pode-se assumir que a codificação mais eficiente é usada. Isto é, binário para inteiros. (Note que nem todo número primo é um primo de Mersenne assim que usar o expoente de Mersenne não é um esquema geral de codificação.)
na criptografia teórica, muitos algoritmos são formalmente passados uma cadeia completamente inútil de K 1 s como o primeiro parâmetro. O algoritmo nunca olha para este parâmetro, mas permite que seja formalmente polinomial em k, que é o parâmetro de segurança usado para afinar a segurança do procedimento.
para alguns problemas para os quais a linguagem de decisão em codificação binária é NP-completo, a linguagem de decisão não é mais NP-completo se a codificação de números incorporados é comutado para unário. As línguas de decisão para outros problemas permanecem NP-completo mesmo nessa altura. Este último é chamado fortemente NP-completo. O exemplo mais conhecido é o empacotamento de caixotes.
é também (e talvez mais) interessante ver como a complexidade de um algoritmo muda se a entrada é comprimida. Para o exemplo de primos de Mersenne, temos visto três codificações, cada uma das quais é logaritmicamente mais comprimida do que seu antecessor.
In 1983, Hana Galperin and Avi Wigderson have written an interesting paper about the complexity of common graph algorithms when the input encoding of the graph is compressed logarithmically. Para estas entradas, a linguagem dos grafos contendo um triângulo de cima (onde estava claramente em P) subitamente se torna NP-completo.
E isso porque classes de linguagem como P e NP são definidas para linguagens, não para problemas.