Estou tentando entender essas classificações e por que elas existem. Meu entendimento está correto? Se não, o que?

1. P é complexidade polinomial ou, para algum número real não negativo , como , etc. Se um problema pertence a P, existe pelo menos um algoritmo que pode resolvê-lo do zero em tempo polinomial. Por exemplo, eu sempre consigo descobrir se algum número inteiro é primo fazendo um loop e verificando a cada passo se ele se divide .O(nk)kO(1), O(n1/2), O(n2), O(n3)n2 <= k <= sqrt(n)kn

2. NP é complexidade polinomial não determinística. Eu realmente não sei o que significa não ser determinístico. Acho que significa que é fácil verificar no tempo polinomial, mas pode ou não ser o tempo polinomial para resolver do zero, se ainda não soubéssemos a resposta. Como pode ser solucionável em tempo polinomial, todos os problemas de P também são problemas de NP. A fatoração inteira é citada como um exemplo de NP, mas não entendo por que não é P, pessoalmente, já que a fatoração de teste leva O(sqrt(n))tempo.

3. NP-Complete Eu não entendo nada, mas o Problema do Vendedor em Viagem é citado como um exemplo disso. Mas, na minha opinião, o problema do TSP pode ser apenas NP, porque é preciso algo como verificar se você recebe o caminho antecipadamente.O(2n n2) time to solve, but O(n)

4. NP-Hard Suponho que esteja cheio de incógnitas. Difícil de verificar, difícil de resolver.

Você está basicamente correto sobre P e NP, mas não sobre NP-hard e NP-complete.

Para iniciantes, aqui estão as definições super concisas das quatro classes de complexidade em questão:

• P é a classe de problemas de decisão que podem ser resolvidos em tempo polinomial por uma máquina de Turing determinística.

• NP é a classe de problemas de decisão que podem ser resolvidos em tempo polinomial por uma máquina de Turing não determinística. Equivalentemente, é a classe de problemas que pode ser verificada em tempo polinomial por uma máquina de Turing determinística.

• NP-hard é a classe de problemas de decisão aos quais todos os problemas no NP podem ser reduzidos no tempo polinomial por uma máquina determinística de Turing.

• NP-complete é a interseção de NP-hard e NP. Equivalentemente, NP-completo é a classe de problemas de decisão no NP, para os quais todos os problemas no NP podem ser reduzidos no tempo polinomial por uma máquina determinística de Turing.

E aqui está um diagrama de Euler da Wikipedia mostrando os relacionamentos entre essas quatro classes (assumindo que P não seja igual a NP):

A parte pela qual suponho que você não está mais familiarizado ou confuso é a noção de uma "redução de tempo polinomial" do problema X para o problema Y. Uma redução de X para Y é simplesmente um algoritmo A que resolve X usando algum recurso outro algoritmo B que resolve o problema Y. Essa redução é chamada de "redução de tempo polinomial" se todas as partes de A, exceto B, tiverem uma complexidade de tempo polinomial. Como um exemplo trivial, o problema de encontrar o menor elemento em uma matriz é redutível em tempo constante ao problema de classificação, já que você pode classificar a matriz e, em seguida, retornar o primeiro elemento da matriz classificada.

Uma coisa fácil de perder na definição de NP-hard é que a redução vai dos problemas de NP para o problema de NP-hard, mas não necessariamente vice-versa . Isso significa que os problemas difíceis de NP podem estar no NP ou em uma classe de complexidade muito maior (como você pode ver no diagrama de Euler), ou talvez nem sejam problemas decidíveis. É por isso que as pessoas costumam dizer algo como "NP-hard significa pelo menos tão difícil quanto NP" ao tentar explicar essas coisas informalmente.

O problema da parada é um bom exemplo de um problema difícil de NP que claramente não está no NP, como a Wikipedia explica :

É fácil provar que o problema de parada é difícil de NP, mas não completo de NP. Por exemplo, o problema de satisfação booleana pode ser reduzido ao problema de parada, transformando-o na descrição de uma máquina de Turing que tenta todas as atribuições de valor de verdade e quando encontra uma que satisfaça a fórmula que para e, caso contrário, entra em um loop infinito. Também é fácil ver que o problema de parada não está no NP, pois todos os problemas no NP são decidíveis em um número finito de operações, enquanto o problema de parada, em geral, é indecidível.

A fatoração inteira é citada como um exemplo de NP, mas não entendo por que não é P, pessoalmente, pois a fatoração de teste leva tempo O (sqrt (n)).

Para fins de classes de complexidade, né o comprimento da entrada. Portanto, se você deseja fatorar um número inteiro k, nnão é ksenão log ko número de bits (ou o que for) necessário para anotar o número. Portanto, a fatoração inteira é O(sqrt(k))como você diz, mas é isso que é .O(sqrt(2n))O(2(n/2))

NP-Hard Suponho que esteja cheio de incógnitas. Difícil de verificar, difícil de resolver.

Não. O NP-Hard é apenas sobre a dificuldade de resolver um problema.

Os problemas NP-Hard são pelo menos difíceis como o problema mais difícil no NP. Sabemos que eles são pelo menos tão difíceis, porque se tivéssemos um algoritmo de tempo polinomial para um problema NP-Hard, poderíamos adaptar esse algoritmo a qualquer problema no NP.

NP-Complete Eu não entendo nada

NP-Complete significa que um problema é NP e NP-Hard. Isso significa que podemos verificar uma solução rapidamente (NP), mas é pelo menos tão difícil quanto o problema mais difícil do NP (NP-Hard).

Eu realmente não sei o que significa não ser determinístico.

O não determinismo é uma definição alternativa de PN. Uma máquina de turing não determinística efetivamente é capaz de duplicar-se a qualquer momento e fazer com que cada duplicata siga um caminho de execução diferente. Sob essa definição, NP é o conjunto de problemas que podem ser resolvidos em tempo polinomial por um computador e que podem se duplicar livremente. Acontece que este é exatamente o mesmo conjunto de problemas que podem ser verificados em tempo polinomial.

A primeira coisa a entender é que P e NP classificam linguagens , não problemas . Para entender o que isso significa, precisamos primeiro de algumas outras definições.

Um alfabeto é um conjunto finito não vazio de símbolos.

{ 0, 1} é um alfabeto, assim como o conjunto de caracteres ASCII. {} não é um alfabeto porque está vazio. N (os números inteiros) não é um alfabeto porque não é finito.

Vamos Σ ser um alfabeto. Uma concatenação ordenada de um número finito de símbolos de Σ é chamada de palavra sobre Σ .

A string 101é uma palavra sobre o alfabeto { 0, 1}. A palavra vazia (geralmente escrita como ε ) é uma palavra sobre qualquer alfabeto. A sequência penguiné uma palavra sobre o alfabeto que contém os caracteres ASCII. A notação decimal do número π não é uma palavra sobre o alfabeto { ., 0, 1, 2, 3, 4, 5, 6, 7, 8, 9} porque não é finito.

O comprimento de uma palavra w , escrita como | w |, é o número de símbolos nele.

Por exemplo, | hello| = 5 e | £ | = 0. Para qualquer palavra w , | w | ∈ N e, portanto, finito.

Vamos Σ ser um alfabeto. O conjunto Σ ^＊ contém todas as palavras sobre Σ , incluindo ε . O conjunto Σ ⁺ contém todas as palavras sobre Σ , excluindo ε . Para n ∈ N , Σ ⁿ é o conjunto de palavras com comprimento n .

Para cada alfabeto Σ , Σ ^* e Σ ⁺ são infinitas conjunto contável . Para o conjunto de caracteres ASCII Σ _ASCII , as expressões regulares .*e .+denotam Σ _ASCII ^＊ e Σ _ASCII ^+, respectivamente.

{ 0, 1} ⁷ é o conjunto de códigos ASCII de 7 bits { 0000000, 0000001, ..., 1111111}. { 0, 1} ³² é o conjunto de valores inteiros de 32 bits.

Vamos Σ ser um alfabeto e L ⊆ Σ ^* . L é chamado de idioma acima de Σ .

Para um alfabeto Σ , o conjunto vazio e Σ ^* são línguas triviais mais de Σ . O primeiro é frequentemente chamado de idioma vazio . O idioma vazio {} e o idioma que contém apenas a palavra vazia { ε } são diferentes.

O subconjunto de { 0, 1} ³² que corresponde a valores de ponto flutuante não NaN IEEE 754 é um idioma finito.

Os idiomas podem ter um número infinito de palavras, mas todos os idiomas são contáveis. O conjunto de cordas { 1, 2, ...} denotando os inteiros em notação decimal é uma linguagem infinita sobre o alfabeto { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. O conjunto infinito de seqüências { 2, 3, 5, 7, 11, 13, ...} denotando os números primos em notação decimal é um subconjunto adequado dos mesmos. O idioma que contém todas as palavras correspondentes à expressão regular [+-]?\d+\.\d*([eE][+-]?\d+)?é um idioma sobre o conjunto de caracteres ASCII (denotando um subconjunto das expressões de ponto flutuante válidas, conforme definido pela linguagem de programação C).

Não há idioma que contenha todos os números reais (em qualquer notação) porque o conjunto de números reais não é contável.

Vamos Σ ser um alfabeto e L ⊆ Σ ^* . Uma máquina D decide G se para cada entrada w ∈ Σ ^* que calcula a função característica χ _G ( w ) em tempo finito. A função característica é definida como

χ G : Σ * → {0, 1}
     w   ↦ 1,   w ∈ L 
         0, caso contrário.

Tal máquina é chamado um decisivo para L . Escrevemos “ D ( w ) = x ” para “dado w , D produz x ”.

Existem muitos modelos de máquinas. O mais geral atualmente em uso prático é o modelo de uma máquina de Turing . Uma máquina de Turing possui armazenamento linear ilimitado agrupado em células. Cada célula pode conter exatamente um símbolo de um alfabeto a qualquer momento. A máquina de Turing executa seu cálculo como uma sequência de etapas de cálculo. Em cada etapa, ele pode ler uma célula, possivelmente substitui seu valor e move a cabeça de leitura / gravação em uma posição para a célula esquerda ou direita. A ação que a máquina 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 de máquina de Turing.

Para o bem desta discussão, não devemos nos incomodar com o modelo preciso da máquina que usamos, mas basta dizer que a máquina possui uma unidade de controle determinística finita, armazenamento ilimitado e executa um cálculo como uma sequência de etapas que podem ser contadas.

Como você o usou em sua pergunta, suponho que você já esteja familiarizado com a notação "big-O", então aqui está apenas uma atualização rápida.

Seja f : N → uma função. O conjunto O ( f ) contém todas as funções g : N → N para as quais existem constantes n ₀ ∈ N e c ∈ N de modo que para cada n ∈ N com n > n ₀ é verdade que g ( n ) ≤ c f ( n )

Agora estamos preparados para abordar a questão real.

A classe P contém todos os idiomas L para os 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 |) etapas para uma função T ∈ O ( n ↦ n ^k ).

Como O ( n ↦ n ^k ), embora matematicamente correto, seja inconveniente para escrever e ler, a maioria das pessoas - para ser honesto, todos , exceto eu - geralmente escreve simplesmente O ( n ^k ).

Observe que o limite depende do comprimento de w . Portanto, o argumento que você cria para o idioma dos números primos é correto apenas para números em codificações desaray , em que para a codificação w de um número n , o comprimento da codificação | w | é proporcional a n . Ninguém jamais usaria essa codificação na prática. Usando um algoritmo mais avançado do que simplesmente tentar todos os fatores possíveis, pode ser mostrado, no entanto, que a linguagem dos números primos permanece em P se as entradas forem codificadas em binário (ou em qualquer outra base). (Apesar do grande interesse, isso só pôde ser comprovado por Manindra Agrawal, Neeraj Kayal e Nitin Saxena em um artigo premiado em 2004, para que você possa adivinhar que o algoritmo não é muito simples.)

Os idiomas triviais {} e Σ ^＊ e o idioma não trivial { ε } estão obviamente em P (para qualquer alfabeto Σ ). Você pode escrever funções em sua linguagem de programação favorita que usam uma string como entrada e retornam um booleano informando se a string é uma palavra do idioma de cada uma delas e provar que sua função possui complexidade de tempo de execução polinomial?

Cada regulares linguagem (a linguagem descrita por uma expressão regular) está em P .

Vamos Σ ser um alfabeto e L ⊆ Σ ^* . Uma máquina V que pega uma tupla codificada de duas palavras w , c ∈ Σ ^＊ e gera 0 ou 1 após um número finito de etapas é um verificador para L se tiver as seguintes propriedades.

• Dado ( w , c ), V saídas 1 somente se W ∈ L .
• Para cada w ∈ G , existe um c ∈ Σ ^* tal que V ( w , c ) = 1.

O C na definição acima é chamado um testemunho (ou certificado ).

Um verificador é permitido dar falsos negativos para a testemunha errado mesmo se w realmente está em L . No entanto, não é permitido dar falsos positivos. Também é necessário que, para cada palavra no idioma, exista pelo menos uma testemunha.

Para o idioma COMPOSITE, que contém as codificações decimais de todos os números inteiros que não são primos, uma testemunha pode ser uma fatoração. Por exemplo, (659, 709)é uma testemunha de 467231∈ COMPOSITE. Você pode verificar facilmente que, em uma folha de papel, sem a testemunha, provar que 467231 não é primo seria difícil sem o uso de 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 todos os idiomas L para os quais existe uma máquina de Turing V que verifica L e uma constante k ∈ N, de modo que, para cada entrada ( w , c ), V pára após no máximo T (| w |) etapas de uma função T ∈ O ( n ↦ n ^k ).

Observe 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 é um superconjunto de P (por quê?). Não se sabe se existem línguas que estão em NP mas não em P .

A fatoração inteira não é um idioma em si. No entanto, podemos construir uma linguagem que represente o problema de decisão associado a ela. Ou seja, uma linguagem que contém todas as tuplas ( n , m ) de modo que n tenha um fator d com d ≤ m . Vamos chamar esse idioma de FACTOR. Se você tiver um algoritmo para decidir o FACTOR, ele poderá ser usado para calcular uma fatoração completa com apenas sobrecarga polinomial, realizando uma pesquisa binária recursiva para cada fator primo.

É fácil mostrar que o FACTOR está em NP . Uma testemunha apropriada seria simplesmente o fator d si e todo o verificador teria que fazer é verificar se 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ítmico em n .)

Se você pode mostrar que o FACTOR também está em P , pode ter certeza de receber muitos prêmios legais. (E você quebrou uma parte significativa da criptografia de hoje.)

Para cada idioma no NP , existe um algoritmo de força bruta que o decide deterministicamente. Simplesmente realiza uma pesquisa exaustiva sobre todas as testemunhas. (Observe que o comprimento máximo de uma testemunha é limitado por um polinômio.) Portanto, seu algoritmo para decidir PRIMES era na verdade um algoritmo de força bruta para decidir COMPOSITE.

Para responder à sua pergunta final, precisamos introduzir redução . Reduções são um conceito muito poderoso de ciência da computação teórica. Reduzir um problema para outro basicamente significa resolver um problema por meio da resolução de outro problema.

Vamos Σ ser um alfabeto e A e B ser línguas mais de Σ . Uma é de tempo polinomial muitos-ona redutível a B se existe uma função f : Σ ^* → Σ ^* com as seguintes propriedades.

• w ∈ A   ⇔   f ( w ) ∈ B   para todos os w ∈ Σ ^＊ .
• A função f pode ser calculada por uma máquina de Turing para cada entrada w em um número de etapas delimitadas por um polinômio em | w |

Neste caso, podemos escrever A ≤ _p B .

Por exemplo, seja A o idioma que contém todos os gráficos (codificados como matriz de adjacência) que contêm um triângulo. (Um triângulo é um ciclo de comprimento 3.) Seja B ainda o idioma que contém todas as matrizes com traço diferente de zero. (O traço de uma matriz é a soma dos seus principais elementos da diagonal.) Então Uma é de tempo polinomial muitos-redutível a um B . Para provar isso, precisamos encontrar uma função de transformação apropriada f . Neste caso, podemos definir f para calcular a 3 ^rd poder da matriz de adjacência. Isso requer dois produtos matriz-matriz, cada um com complexidade polinomial.

É trivialmente verdade que L ≤ _p L . (Você pode provar isso formalmente?)

Vamos aplicar isso ao NP agora.

Uma linguagem L é NP - difícil se e somente se L '≤ _p L para cada idioma L ' ∈ NP .

Um idioma NP- difícil pode ou não estar no próprio NP .

Um idioma L é NP - completo se e somente se

• L ∈ NP e
• L é NP- duro.

A linguagem mais famosa de NP- completo é SAT. Ele contém todas as fórmulas booleanas que podem ser satisfeitas. Por exemplo, ( a ∨ b ) ∧ (¬ a ∨ ¬ b ) AT SAT. Uma testemunha válida é { a = 1, b = 0}. A fórmula ( a ∨ b ) ∧ (¬ a ∨ b ) ¬ b ∉ SAT. (Como você provaria isso?)

Não é difícil mostrar que SAT ∈ NP . Mostrar a dureza NP do SAT é um trabalho, mas foi feito em 1971 por Stephen Cook .

Uma vez conhecido esse idioma completo NP , era relativamente simples mostrar a completude NP de outros idiomas via redução. Se a linguagem A é conhecida por ser NP- difícil, então mostra que A ≤ _p B mostra que B também é NP- difícil (através da transitividade de "≤ _p "). Em 1972, Richard Karp publicou uma lista de 21 idiomas que ele poderia mostrar como NP-completa via redução (transitiva) de SAT. (Este é o único documento 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 funciona a comprovação da completude do NP via redução.)

Finalmente, um breve resumo. Usaremos os símbolos NPH e NPC para denotar as classes dos idiomas NP- hard e NP- complete respectivamente.

• P ⊆ NP
• NPC ⊂ NP e NPC ⊂ NPH , na verdade NPC = NP ∩ NPH por definição
• ( A ∈ NP ) ∧ ( B ∈ NPH ) ⇒   A ≤ _p B

Observe que a inclusão NPC ⊂ NP é adequada mesmo no caso de P = NP . Para ver isso, deixe claro que nenhuma linguagem não trivial pode ser reduzida a uma linguagem trivial e existem idiomas triviais em P , bem como idiomas não triviais em NP . Este é um argumento (não muito interessante).

Termo aditivo

Sua principal fonte 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 na verdade se refere ao comprimento da entrada. Essa é uma distinção importante porque significa que a complexidade assintótica de um algoritmo depende da codificação usada para a entrada.

Nesta semana, foi alcançado um novo recorde para o maior primo conhecido de Mersenne . O maior número primo atualmente conhecido é 2 ^{74 207 281} - 1. Esse número é tão grande que me causa dor de cabeça; portanto, usarei um número menor no exemplo a seguir: 2 ³¹ - 1 = 2 147 483 647. Ele pode ser codificado de maneiras diferentes.

• pelo seu expoente Mersenne como número decimal: 31(2 bytes)
• como número decimal: 2147483647(10 bytes)
• como número unário: em 11111…11que o …deve ser substituído por 2 147 483 640 mais 1s (quase 2 GiB)

Todas essas cadeias codificam o mesmo número e, dado qualquer uma delas, podemos facilmente construir qualquer outra codificação do mesmo número. (Você pode substituir a codificação decimal por binária, octal ou hexadecimal, se desejar. Isso altera apenas 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 de Lucas-Lehmer é o algoritmo mais conhecido para Mersenne inicia M _p com p um primo ímpar, mas ainda é exponencial no comprimento da codificação binária do expoente de Mersenne p (polinômio em p ).

Se quisermos falar sobre a complexidade de um algoritmo, é muito importante esclarecermos com precisão a representação que usamos. Em geral, pode-se supor que a codificação mais eficiente seja usada. Ou seja, binário para números inteiros. (Observe que nem todo número primo é um primo Mersenne, portanto, o uso do expoente Mersenne não é um esquema geral de codificação.)

Na criptografia teórica, muitos algoritmos passam formalmente por uma sequência completamente inútil de k 1 s como o primeiro parâmetro. O algoritmo nunca analisa esse parâmetro, mas permite que ele seja formalmente polinomial em k , que é o parâmetro de segurança usado para ajustar a segurança do procedimento.

Para alguns problemas para os quais a linguagem de decisão na codificação binária é NP- completa, a linguagem de decisão não é mais NP- completa se a codificação de números incorporados for alterada para unária. As linguagens de decisão para outros problemas permanecem NP- completas mesmo assim. Estes últimos são chamados fortemente de NP- completos . O exemplo mais conhecido é o empacotamento de caixas .

Também é (e talvez mais) interessante ver como a complexidade de um algoritmo muda se a entrada é compactada . Para o exemplo de primos de Mersenne, vimos três codificações, cada uma das quais é logaritmicamente mais compactada que seu antecessor.

Em 1983, Hana Galperin e Avi Wigderson escreveram um artigo interessante sobre a complexidade de algoritmos comuns de gráfico quando a codificação de entrada do gráfico é compactada logaritmicamente. Para essas entradas, a linguagem dos gráficos contendo um triângulo de cima (onde estava claramente em P ) repentinamente se torna NP .

E isso ocorre porque classes de idiomas como P e NP são definidas para idiomas , não para problemas .

Vou tentar lhe dar uma definição menos informal para o mesmo.

Problemas de P: problemas que podem ser resolvidos em tempo polinomial. Contém problemas que podem ser solucionados com eficiência.

Problema NP: problemas que podem ser verificados em tempo polinomial. Por exemplo: Vendedor ambulante, projeto de circuitos. Os problemas de NP são como quebra-cabeças (como sudoku). Dada uma solução correta para o problema, podemos verificar nossa solução com muita rapidez, mas se realmente tentarmos resolvê-la, pode levar uma eternidade.

Agora, P vs NP realmente pergunta se um problema cuja solução pode ser rapidamente verificada para estar correto, existe sempre uma maneira rápida de resolvê-lo. Assim, escrevendo em termos matematicamente: NP é um subconjunto de P ou não?

Agora voltando ao NP completo: esses são os problemas realmente difíceis dos problemas do NP. Portanto, se houver uma maneira mais rápida de resolver NP complete, NP complete se tornará um problema de P e NP entrando em P.

NP rígido: problemas que não podem ser verificados no tempo polinomial são np difíceis. Por exemplo, escolher a melhor jogada no xadrez é uma delas.

Se algo não estiver claro, tente assistir a este vídeo: https://www.youtube.com/watch?v=YX40hbAHx3s

Espero que isso forneça algum contorno embaçado.