Você está basicamente correto sobre P e NP, mas não sobre NP-difícil e NP-completo.

Para começar, aqui estão as definições superconcisas 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 podem ser verificados em tempo polinomial por uma máquina de Turing determinística.

• NP-difícil é a classe de problemas de decisão para a qual todos os problemas em NP podem ser reduzido a em tempo polinomial por uma máquina de Turing determinística.

• NP-completo é a interseção de NP-difícil e NP. Equivalentemente, NP-completo é a classe de problemas de decisão em NP à qual todos os outros problemas em NP podem ser reduzidos em tempo polinomial por uma máquina de Turing determinística.

E aqui Diagrama de “sa Euler da Wikipedia mostrando as relações entre essas quatro classes (assumindo que P não é igual a NP):

A parte que suponho que você “não esteja 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 fazendo uso de algum 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, uma vez que você pode classificar a matriz e, em seguida, retornar o primeiro elemento da matriz classificada.

Um coisa que é fácil perder sobre a definição NP-difícil é que a redução vai de problemas NP-difíceis para o problema NP-difícil, mas não necessariamente vice-versa . Isso significa que problemas NP-difíceis podem ser em NP, ou em uma classe de complexidade muito mais alta (como você pode ver no diagrama de Euler), ou eles podem nem mesmo ser problemas decidíveis.É por isso que as pessoas costumam dizer algo como “NP-difícil 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 NP-difícil que “claramente não está em NP, como Wikipedia explica :

É fácil provar que o problema da parada é NP-difícil, mas não NP-completo. Por exemplo, o problema de satisfatibilidade booleana pode ser reduzido ao problema da 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, ela para e, caso contrário, entra em um loop infinito. Também é fácil ver que o problema da parada não está em NP, já que todos os problemas em NP são decidíveis em um número finito de operações, enquanto o problema da parada, em geral, é indecidível.

Comentários

• @Nakano Intuitivamente, ele ‘ sa ” redução ” no sentido de que um problema está sendo transformado em subproblema de algum outro problema. O fato de algumas dessas reduções aumentarem a complexidade em vez de diminuí-la por meio de uma escolha inadequada de ” subproblema ” simplesmente significa que você nunca usaria essas reduções em qualquer código do mundo real. Embora, para ser honesto, NP-hard me pareça uma classe estranha e não muito interessante; pode ser mais proveitoso ignorá-lo e apenas pensar em NP-completo como o conjunto de problemas NP a que todos os outros problemas NP se reduzem.
• @Nakano stackoverflow.com/questions/12637582/… Acredito que a resposta curta é que quando as pessoas falam sobre a fatoração de inteiros sendo NP, elas ‘ normalmente está falando sobre inteiros realmente grandes, para os quais você geralmente começa a fazer suas provas big-O com n como ” o número de bits que o inteiro ocupa na memória ” em vez de ” o número de inteiros que você passou para a função “.
• @Nakano: Na notação big-O, o n é uma medida para o tamanho da entrada (número de elementos, bytes, dígitos, etc.), não o valor do entrada.
• @Nakano A resposta curta é que você ‘ está bem, e é por isso que quando você cumpre pena análise de mplexidade você sempre precisa especificar o que n significa . A afirmação de que n é ” o tamanho da entrada ” é meramente um resumo conciso de como normalmente escolhemos definir n. Ele ‘ não faz parte das definições rigorosas de notação big-O ou complexidade de tempo. Eu acredito que você está correto em dizer que a fatoração de inteiros é O (sqrt (n)) quando n é o valor da entrada. Acontece que os resultados de complexidade em que n significa tamanho são geralmente muito mais úteis na prática do que aqueles em que n significa valor.
• @Nakano It ‘ Também vale a pena ter em mente que tecnicamente você também deve definir a complexidade de tempo de suas operações primitivas (adição, multitplicação, leitura da memória, gravação na memória, comparação de dois números). Na maioria das vezes, presumimos que todas essas primitivas são constantes ou contamos apenas um tipo de operação (por exemplo, para algoritmos de classificação, tradicionalmente contamos as comparações). Suspeito que os resultados da fatoração de inteiros não ‘ assumem que todas essas operações são constantes no tempo, como costumamos fazer, caso contrário, o tamanho do número não ‘ importa muito.

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

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

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

Não. NP-Difícil trata apenas de quão difícil é um problema de resolver.

Problemas NP-Difícil são pelo menos difíceis como o problema mais difícil em 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-difícil, poderíamos adaptar esse algoritmo a qualquer problema em NP.

NP-Completo Eu não entendo

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

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

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

Comentários

• Portanto, é possível para $ O ( n ^ k) Algoritmos de $ time para serem problemas NP?
• k é um número real constante? sim. Todos os problemas P também são problemas NP. Obviamente, qualquer coisa que você possa resolver em tempo polinomial também pode ser verificado em tempo polinomial.
• Como o comprimento / tamanho é realmente definido aqui? Por exemplo, eu poderia simplesmente escrever $ n $ em uma base grande e diminuir seu comprimento ao escrever. E os problemas que não ‘ explicitamente lidam com números inteiros, mas digamos gráficos com $ V $ vértices e $ E $ arestas, etc.
• @Nakano, na verdade uma grande base não ‘ mudaria isso, porque seria apenas uma diferença de fator constante. Portanto, não ‘ t efeito polinomial versus não polinomial. No entanto, se você escrevesse o número em unário, ele o mudaria.
• @Nakano, hmm … Eu não ‘ ousaria tentar explicar a complexidade aulas para uma criança de cinco anos. : P

A primeira coisa a entender é que P e NP classifica línguas , 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 inteiros) não é um alfabeto porque não é finito.

Vamos Σ seja 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 string 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 Σ seja 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 de comprimento n .

Para cada alfabeto Σ , Σ ^＊ e Σ ⁺ são infinitos conjuntos contáveis .Para o conjunto de caracteres ASCII Σ _ASCII , as expressões regulares .* e .+ denota Σ _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.

Seja Σ um alfabeto e L ⊆ Σ ^＊ . L é chamado de linguagem sobre Σ .

Para um alfabeto Σ , o conjunto vazio e Σ ^＊ são linguagens triviais em Σ . O primeiro é freqüentemente chamado de linguagem vazia . 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 é uma linguagem finita.

Os idiomas podem ter um número infinito de palavras, mas todos os idiomas são contáveis. O conjunto de strings {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 strings {2, 3, 5, 7, 11, 13,…} denotando que os números primos em notação decimal é um subconjunto apropriado deles. A linguagem que contém todas as palavras que correspondem à expressão regular [+-]?\d+\.\d*([eE][+-]?\d+)? é uma linguagem 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á linguagem 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 L se para cada entrada w ∈ Σ ^＊ ele calcula a função característica χ _L ( w ) em tempo finito. A função característica é definida como

χL: Σ＊ → {0, 1} w ↦ 1, w ∈ L 0, otherwise.

Essa máquina é chamada de decisor para L . Escrevemos “ D ( w ) = x ” para “dado w , D saídas x ”.

Existem muitos modelos de máquina. 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 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 sobrescrever seu valor e mover o cabeçote de leitura / gravação em uma posição para a célula esquerda ou direita. A ação da máquina é controlada por um autômato de estados finitos.

Uma máquina de acesso aleatório com um conjunto finito de instruções e armazenamento ilimitado é outro modelo de máquina tão poderoso quanto o modelo de máquina de Turing.

Para o propósito desta discussão, não devemos nos incomodar com o modelo de máquina preciso que usamos, mas sim o suficiente para dizer que a máquina tem uma unidade de controle determinística finita, armazenamento ilimitado e executa um cálculo como uma sequência de etapas isso pode ser contado.

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

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

Agora estamos preparados para abordar a questão real.

A classe 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 de modo que para cada entrada w , D para após no máximo T (| w |) etapas para uma função T ∈ O ( n ↦ n ^k ).

Desde O ( n ↦ n ^k ), embora matematicamente correto, é inconveniente de 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ê faz para a linguagem dos primos só é correto para números em codificações unaray , onde para a codificação w de um número n , o comprimento da codificação | w | é proporcional a n . Ninguém jamais usaria tal codificação na prática. Usando um algoritmo mais avançado do que simplesmente tentar todos os fatores possíveis, pode-se mostrar, entretanto, que a linguagem dos números primos permanece em P se as entradas forem codificadas em binário (ou para qualquer outra base). (Apesar do enorme interesse, isso só pôde ser provado por Manindra Agrawal, Neeraj Kayal e Nitin Saxena em um jornal premiado em 2004, então você pode adivinhar que o algoritmo não é muito simples.)

As linguagens triviais {} e Σ ^＊ 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 receba uma string como entrada e retorne um booleano informando se a string é uma palavra da linguagem para cada uma delas e provar que sua função tem complexidade de tempo de execução polinomial?

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

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

• Dado ( w , c ), V gera 1 apenas se w ∈ L .
• Para cada w ∈ L , há existe um c ∈ Σ ^＊ de modo que V ( w , c ) = 1.

O c na definição acima é chamado de testemunha (ou certificado ) .

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

Para o idioma COMPOSTO, 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 de 467231 ∈ COMPOSTO. Você pode facilmente verificar isso em uma folha de papel sem a testemunha dada, provar que 467231 não é primo seria difícil sem usar um computador.

Não dissemos nada sobre como uma testemunha adequada pode ser encontrado. 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 L e uma constante k ∈ N de modo que para cada input ( w , c ), V para depois de no máximo T (| w |) etapas para 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 linguagens que estão em NP , mas não em P .

A fatoração de inteiros não é uma linguagem per se. 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 forma que n tenha um fator d com d ≤ m . Chamemos essa linguagem de FATOR. Se você tiver um algoritmo para decidir FACTOR, ele pode 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 FACTOR está em NP . Uma testemunha apropriada seria simplesmente o próprio fator d e tudo o que 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ê puder mostrar que FACTOR também está em P , você receberá muitos prêmios legais. (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 executa uma pesquisa exaustiva em 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 COMPOSTO.

Para responder à sua pergunta final, precisamos apresentar a redução . As reduções são um conceito muito poderoso da ciência da computação teórica. Reduzir um problema a outro basicamente significa resolver um problema resolvendo outro problema.

Seja Σ um alfabeto e A e B ser idiomas acima de Σ . A é muitos-um em tempo polinomial redutível para B se houver uma função f : Σ ^＊ → Σ ^＊ com as seguintes propriedades.

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

Neste caso, escrevemos A ≤ _p B .

Para Por exemplo, seja A a linguagem 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 ainda B a linguagem que contém todas as matrizes com traço diferente de zero. (O traço de uma matriz é a soma de seus principais elementos diagonais.) Então A é polinomial-tempo muitos-um redutível a B . Para provar isso, precisamos encontrar uma função de transformação apropriada f . Nesse caso, podemos definir f para calcular a 3 ^rd potência da matriz de adjacência. Isso requer dois produtos matriz-matriz, cada um dos quais com complexidade polinomial.

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

Vamos aplicar isso ao NP agora.

Um idioma L é NP -hard se e somente se L “≤ _p L para todos os idiomas L ” ∈ NP .

Uma linguagem difícil de NP pode ou não estar no próprio NP .

Um idioma L é NP -complete se e somente se

• L ∈ NP e
• L é NP -difícil.

A linguagem completa do NP mais famosa é o SAT. Ele contém todas as fórmulas booleanas que podem ser satisfeitas. Por exemplo, ( a ∨ b ) ∧ (¬ a ∨ ¬ b ) ∈ 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 dá trabalho, mas foi feito em 1971 por Stephen Cook .

Uma vez que aquele NP -completo da linguagem era conhecido, era relativamente simples mostrar o NP -completo de outras linguagens por meio de redução. Se o idioma A for conhecido como NP -duro, então mostrando que A ≤ _p B mostra que B também é NP -difícil (por meio da transitividade de “≤ _p ”). Em 1972, Richard Karp publicou uma lista de 21 línguas que ele poderia mostrar que eram NP -completas via redução (transitiva) de 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 funciona a comprovação do NP -completude via redução. )

Finalmente, um breve resumo. Usaremos os símbolos NPH e NPC para denotar as classes das linguagens NP -duro e NP -completa 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 trivial e também há linguagens triviais em P como linguagens não triviais em NP . Thi s é um caso secundário (não muito interessante).

Adendo

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. 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 registro para o maior Mersenne prime foi alcançado. O maior número primo conhecido atualmente é 2 ^{74   207   281} – 1. Este número é tão grande que me dá dor de cabeça, então “usarei um menor no exemplo a seguir: 2 ³¹ – 1 = 2   147   483   647. Pode ser codificado de maneiras diferentes.

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

Todas essas strings 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 hexadeci mal se você quiser. Ele apenas altera 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 primos de Mersenne 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 que estejamos muito claros sobre a representação que usamos. Em geral, pode-se supor que a codificação mais eficiente é usada. Ou seja, binário para inteiros. (Observe que nem todo número primo é um primo de Mersenne, portanto, usar o expoente de Mersenne não é um esquema de codificação geral.)

Na criptografia teórica, muitos algoritmos recebem formalmente uma string 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 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ário. As linguagens de decisão para outros problemas permanecem NP completas mesmo então. Os últimos são chamados de fortemente NP -completos . O exemplo mais conhecido é embalagem de lixo .

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

Em 1983, Hana Galperin e Avi Wigderson escreveu um artigo interessante sobre a complexidade dos algoritmos de gráfico comuns 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 torna-se NP completa.

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

Comentários

• Esta resposta provavelmente não é útil para o nível de compreensão de quem pergunta. Leia as outras respostas e veja no que Nanako está lutando. Você acha que isso a resposta irá ajudá-lo?
• Esta resposta pode não ajudar o OP, mas certamente ajuda outros leitores (inclusive eu).
• resposta muito útil! deve considerar corrigir os símbolos matemáticos de forma inadequada exibido.

Vou tentar dar a você uma definição menos informal para o mesmo.

Problemas P: problemas que podem ser resolvidos em tempo polinomial. Contém problemas que podem ser resolvidos de forma eficiente.

Problema NP: problemas que podem ser verificados em polyno hora inicial. Por exemplo: caixeiro viajante, desenho de circuitos. Os problemas NP são como quebra-cabeças (como sudoku). Dada uma solução correta para o problema, podemos verificar nossa solução muito rapidamente, mas se realmente tentarmos resolvê-la, pode levar uma eternidade.

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

Agora, voltando ao NP completo: esses são os problemas realmente difíceis dos problemas NP. Portanto, se existe uma maneira mais rápida de resolver NP completo, então NP completo se torna P e os problemas NP se transformam em P.

NP difícil: 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 desfocado.