A complexidade de problemas fortemente difíceis ou incompletos de NP muda quando sua entrada é codificada em unário?

12

A dificuldade de um problema fortemente NP-difícil ou NP-completo (como por exemplo, definido aqui ) muda quando sua entrada é unária em vez de codificada em binária?

Que diferença faz se a entrada de um problema fortemente NP-difícil é unária? Quero dizer, se eu pegar, por exemplo, o problema fracassado de NP-Complete Knapsack, ele é NP-completo quando codificado em binário, mas pode ser resolvido em tempo polinomial por programação dinâmica quando codificado em unário. Talvez isso tenha implicações na dureza de níveis mais altos da hierarquia polinomial do tempo?

A noção de fortemente ...- também vale para outras classes de complexidade, por exemplo, classes mais altas da hierarquia polinomial do tempo?

Eu já fiz essa pergunta no stackoverflow.com, mas foi destacado que é mais apropriado aqui.

complexity-theory time-complexity np-complete user2145167
fonte

Talvez eu deva fazer essa pergunta melhor em cstheory.stackexchange.com ? Eu simplesmente não sabia que existia. As perguntas aqui não vão na direção que eu esperava.

user2145167

Por que eles não? Eles estão (até onde eu sei) corretos, então talvez sua pergunta não seja a que você deseja fazer? Além disso, a Ciência da Computação Teórica é para questões de TCS no nível de pesquisa , que certamente não é essa.

Raphael

4

Um tamanho de problema de codificado em unário é o tamanho e o se binário. Se o tempo gasto for , este será no primeiro caso e no segundo caso. Portanto, um algoritmo polinomial para o primeiro caso provavelmente será exponencial para o segundo. A codificação do problema pode alterar radicalmente a complexidade de um algoritmo. $N$ $N$ $\log N$ $F(N)$ $F(\text{size})$ $F(2^{\text{size}})$

vonbrand
fonte

3

Não.

Se você alterar a codificação da entrada, alterou a definição formal do problema, o que significa que é um problema diferente . A complexidade do problema original não muda, pela mesma razão que apontar para uma luz diferente no céu não altera a massa da lua.

JeffE
fonte

2

P

$P$

P_{1}

$P_1$

2

A resposta curta é que, se a entrada for unária, ela será mais longa . É exponencialmente mais longo. Agora, um algoritmo que funciona em tempo polinomial no tamanho da entrada tem "tempo suficiente" para resolver o problema, apenas porque a entrada em si é exponencialmente maior que a do problema original.

Tocou.
fonte

1

Vendo a questão da formulação apontada na resposta de JeffE, a resposta é sim.

Considere o problema da mochila . Ele possui um algoritmo pseudo-polinomial , que é aquele com tempo de execução limitado por um polinômio em um número codificado na entrada. Como na codificação unária os valores correspondem ao comprimento, esse é um algoritmo de tempo polinomial para a versão unária.

De fato, todo problema fracamente completo de NP se enquadra nessa categoria.

Rafael
fonte

Pergunta secundária, mas eu nunca entendi - como você "codifica" algo em unário? Você não precisa de um delimitador de algum tipo?

user541686

@Mehrdad Sim e não. Sim; símbolos de separação geralmente não são contados nesse sentido, cf também entrada vs alfabeto de fita; aqui consideramos apenas o tamanho do alfabeto de entrada. Não; em princípio, um número é suficiente para codificar tuplas e conjuntos de números contáveis, para que você não precise de símbolos de separação. Isso claramente não é útil para "trabalhar" com essas máquinas, mas justifica ignorar os símbolos de separação (e outros controles).

Raphael

Hmm ... não sei se entendi sua parte "não"; como você saberia onde termina o número se não tivesse um separador no final? Parece um pouco de lógica circular para mim: se estamos ignorando separadores, então efetivamente a questão se torna "se forçarmos a entrada a ocupar exponencialmente mais espaço, isso altera o tempo de execução de um algoritmo exponencial em relação ao tamanho da entrada?" ? " cuja resposta é trivialmente sim ... por definição. Não é tanto alterar a codificação, como adicionar artificialmente bits redundantes quando você leva em conta os separadores.

user541686

@ Mehrdad Ok, eu só estava pensando em separar vários números um do outro. Em qualquer caso, você precisa de marcadores finais resp. símbolos "vazios" nas máquinas de Turing; das quais você não pode se livrar. O restante você pode codificar no número único (com uma penalidade de execução, obviamente).

Raphael

A complexidade de problemas fortemente difíceis ou incompletos de NP muda quando sua entrada é codificada em unário?

Respostas:

Não.