O que é a classe de complexidade NPI? – terminologia complexidade-de-algoritmo teoria-da-computação

Pergunta:


Estudando sobre complexidade, me deparei com o termo NPI. Ele significa NP-intermediário. Mas não entendi o que é esse “intermediário”.

  • O que caracteriza um problema NPI? Por que ela tem esse nome?
  • Existe diferença entre NPI e NPC?
  • Alguma coisa muda em relação a essa classe caso se descubra a resposta ao problema P vs NP?

Autor da pergunta Jefferson Quesado

Resposta Victor Stafusa:

Os problemas P são os que admitem solução determinística em tempo polinomial.

Os problemas NP são os que admitem solução não-determinística em tempo polinomial (ou seja, se você ver uma possível resposta em uma bola de cristal, poderá verificar se está ou não correta em tempo polinomial).

Os problemas NP-completos (NPC) são os “mais difíceis de NP”, reduzindo-se em tempo polinomial uns aos outros. Há diversos problemas sabidamente NP-completos conhecidos por aí, tal como satisfatibilidade, caixeiro viajante, caminho hamiltoniano, etc. Se um deles for demonstrado estar em P, então todos os problemas de NP estariam em P e com isso P = NP.

Entretanto, tomando-se a premissa de que P ≠ NP, vem a pergunta: Será que todos os problemas que estão em NP obrigatoriamente estão em P ou em NPC? Ou será que haveria problemas em NP que não estão em nenhuma dessas duas categorias? Aí é que entra o NPI.

A classe NPI corresponde ao conjunto de problemas que estão em NP, mas não estão nem em NPC e nem em P. São problemas para os quais não há solução determinística em tempo polinomial (não estão em P), mas ainda assim uma possível solução pode ser verificada em tempo polinomial (estão em NP) e não são NP-completos:

NPC + P + NPI = NP

Richard Ladner demonstrou em 1975, que se P ≠ NP então existem problemas dentro de NP que não estão nem em P e nem em NPC, foi com ele que surgiu a classe NPI. Ela tem esse nome (NP intermediário) porque não são nem os mais difíceis de NP (NPC) e nem os mais fáceis (P). Logo, estão em uma categoria intermediária.

Não se conhecem problemas reais que definitivamente estão em NPI. Até porque se para provar que um problema é NPI, você teria que provar que ele está em NP, mas está fora de P, e com isso você teria que provar primeiro que P ≠ NP antes de provar que algum problema particular está em NPI. Apesar disso, há alguns problemas suspeitos de estarem nessa área, os mais célebres são:

  • Fatoração de números
  • Logaritmo discreto
  • Isomorfismo de grafos

Peguemos o problema da fatoração:

  • Seja x o número que você quer fatorar. Se você ver numa bola de cristal uma sequência de números primos que supostamente multiplicados resultam em x, você pode facilmente fazer a multiplicação e conferir se de fato eles produzem ou não x, logo esse problema está em NP.

  • Não se conhece algoritmo eficiente para fatorar-se números grandes. Supondo que de fato nenhum exista, então esse problema não está em P.

  • Não se conhece forma de reduzir-se o problema da satisfatibilidade ao problema da fatoração em tempo polinomial, e supondo que tal redução de fato não exista, o problema da fatoração não é NPC. De fato, os problemas NPC parecem ser significativamente mais complexos que o da fatoração.

  • Logo, se essas suposições forem verdadeiras, o problema da fatoração é NPI.

Fonte

Related Posts:

Qual a diferença entre AppCompatActivity e Activity? – android android-activity
Pergunta: Qual a diferença da AppCompatActivity para Activity ? A partir de qual versão a AppCompatActivity foi adicionada ao Android? Autor da pergunta Luhhh A diferença reside ...
Como abreviar palavras em PHP? – php string
Pergunta: Possuo informações comuns como nome de pessoas e endereços, e preciso que elas contenham no máximo 30 caracteres sem cortar palavras. Exemplo: 'Avenida Natalino João Brescansin' ...
Qual é a finalidade de um parêntese vazio numa declaração Lambda? – c# expressões-lambda característica-linguagem
Pergunta: Criei um exemplo de uma declaração Lambda sem argumentos, entretanto, estou com duvidas referente a omissão do parêntese vazio () na declaração. Veja o exemplo: class ...
Boas práticas para URI em API RESTful – api rest restful
Pergunta: Estou com dúvida em relação às URIs de alguns recursos da api que estou desenvolvendo. Tenho os recursos projetos e atividades com relação 1-N, ...
Dúvidas sobre a integração do MySQL com Java – java mysql netbeans
Pergunta: Estou criando um sistema no NetBeans, utilizando a linguagem Java e o banco de dados MySQL. Escrevi o seguinte código para realizar a conexão ...
Qual é a finalidade da pasta Model do framework Inphinit? – php inphinit
Pergunta: No Inphinit micro-framework existe a pasta Model que fica dentro da pasta application, e nela é onde ficam as classes, mas eu estou muito ...
Uso do ‘@’ em variáveis – javascript typescript coffeescript
Pergunta: Vejo em algumas linguagens que compilam para javascript, como TypeScript e CoffeeScript, o uso do @ em variáveis, como também, casos em que o ...
Qual tamanho máximo um arquivo JSON pode ter? – json arquivo
Pergunta: Vou dar um exemplo para conseguir explicar minha duvida: Preciso recuperar informação de imagens vindas de uma API, esse banco de imagens me retorna JSON's ...
O que é Teste de Regressão? – terminologia engenharia-de-software testes
Pergunta: Na matéria de Teste de Software o professor abordou um termo chamado Teste de Regressão, isto dentro da disciplina de teste de software. Sendo ...
O que é um construtor da linguagem? – php característica-linguagem
Pergunta: Em PHP, já li e ouvi várias vezes a respeito dos Construtores da Linguagem. Os casos que sempre ouvi falar deles foi em casos ...
Função intrínseca para converter numérico para string – cobol
Pergunta: Estou a tentar saber se existe alguma função intrínseca do COBOL para converter um data numérico para string sem precisar usar a cláusula REDEFINES: ( ...
Porque usar implements? – java android
Pergunta: Qual a diferença entre usar btn.setOnClickListener(new OnClickListener() { e public class MainActivity extends Activity implements OnClickListener{ Estive fazendo um curso de Android e meu professor falou que ...
O que é XHTML e quando deve ser usado? – html xml xhtml
Pergunta: O que eu sei é que o XHTML precisa ser XML válido. Isso implica, por exemplo, que todas as tags precisam ser fechadas. Por ...
Uma placa aceleradora de vídeo pode melhorar o desempenho não-gráfico? [fechada] – desempenho
Pergunta: Para desenvolver em Ruby on Rails, eu utilizo aqui uma máquina virtual do VirtualBox com Ubuntu Server 14.04 sem interface gráfica instalada. Recentemente descobri uma ...
Concat() VS Union() – c# .net
Pergunta: Qual a diferença entre Concat() e Union() ? Quando usar Concat() e quando usar Union() ? Somente pode ser usado em list ? ...

Deixe uma resposta

O seu endereço de email não será publicado. Campos obrigatórios marcados com *