O melhor tempo de execução para resolver um problema de preenchimento de NP?

Question

Qual é o algoritmo mais rápido que existe para resolver um problema de preenchimento de NP específico? Por exemplo, uma implementação ingênua de vendedor ambulante é o (n!), mas com programação dinâmica, pode ser feito em O (n^2 * 2^n). Existe algum problema talvez "mais fácil" de NP que tenha um melhor tempo de execução?

Estou curioso sobre soluções exatas, não aproximações.

Answer 1

...] Com programação dinâmica, pode ser feito em O (n^2 * 2^n). Existe algum problema talvez "mais fácil" de NP que tenha um melhor tempo de execução?

Tipo de. Você pode se livrar de qualquer fator polinomial criando um problema artificial que codifica a mesma solução em uma entrada polinomialmente maior. Desde que a entrada seja apenas polinomialmente maior, o problema resultante ainda será premiado NP. Como a complexidade é, por definição, a função que mapeia o tamanho da entrada para o tempo de execução, se o tamanho da entrada crescer, a função entrará nas classes mais baixas do O.

Portanto, o mesmo algoritmo que executa no TSP com a entrada acolchoada com n^2 bits inúteis terá complexidade O (1 * 2^sqrt (n)).

Answer 2

Uma característica dos problemas de preenchimento de NP é que qualquer um dos problemas no NP pode ser mecanicamente transformado em qualquer um dos problemas completos de NP em, no máximo, tempo polinomial.

Portanto, qualquer que seja a melhor solução para um determinado problema de NP, é automaticamente uma solução semelhante para qualquer outro problema de NP.

Dado que a programação dinâmica pode resolver o problema do vendedor ambulante no tempo 2^n e no espaço, o mesmo deve ser verdadeiro para todos os outros problemas de NP [bem, além de tempo para aplicar a transformação, eu acho - para que possa ser 2^ (n+1)].

Answer 3

Geralmente você não pode encontrar o melhor Solução para o problema genérico de vendedor ambulante sem experimentar todas as combinações (pode haver distâncias negativas, etc.).

Adicionando restrições adicionais e afrouxando o requisito de obter o melhor Solução, você pode acelerar bastante as coisas.

Por exemplo, você pode obter tempo executável polinomial se as distâncias no problema obedecer a "não é mais para ir diretamente de A a B do que ir de A a C a B" (ou seja, um atalho nunca é mais), e Você pode viver com o resultado sendo o máximo de 1,5 vezes o valor ideal. Ver http://en.wikipedia.org/wiki/travelling_salesman_problem#metric_tsp