TSP euclidiano em NP e complexidade de raiz quadrada

12

Nas notas de aula de Ola Svensson: http://theory.epfl.ch/osven/courses/Approx13/Notes/lecture4-5.pdf , diz-se que não sabemos se o TSP euclidiano está em NP:

A razão é que não sabemos como calcular raízes quadradas com eficiência.

Por outro lado, há este artigo de Papadimitriou: http://www.sciencedirect.com/science/article/pii/0304397577900123 dizendo que é NP-completo, o que também significa que está em NP. Embora ele não prove isso no jornal, acho que ele considera a participação no NP trivial, como geralmente ocorre com esses problemas.

Eu estou confusa com isso. Honestamente, a alegação de que não sabemos se o TSP Euclidiano está em NP me chocou, já que eu apenas assumi que é trivial - tomando o tour pelo TSP como um certificado, podemos verificar facilmente se é um tour válido. Mas o problema é que pode haver algumas raízes quadradas. Portanto, as notas da palestra afirmam basicamente que não podemos, em tempo polinomial, resolver o seguinte problema:

Dado o número racional , decida se .q1,,qn,AQq1++qnA

Pergunta 1: O que sabemos sobre esse problema?

Isso implora a seguinte simplificação, que não consegui encontrar:

Pergunta 2: Isso é redutível ao caso especial quando ? Esse caso especial pode ser resolvido em tempo polinomial?n=1

Pensando nisso por um tempo, cheguei a isso. Queremos complexidade de tempo polinomial com relação ao número de bits da entrada, ou seja, não ao tamanho dos próprios números. Podemos facilmente calcular a soma para um número polinomial de dígitos decimais. Para obter um caso incorreto, precisamos de uma instância de para tais que para cada polinômio , existe um número inteiro tal que e concordam com os primeiros dígitos de expansão decimal. k = 1 , 2 , p k q1,k,,qn,k,AkQk=1,2,pk Akp(tamanho da entrada)q1,k++qn,kAkp(input-size)

Pergunta 3: Existe um exemplo de número reacional?

Mas o que é ? Isso depende da maneira como os números racionais são representados! Agora estou curioso sobre isso:input-size

Pergunta 4: É algoritmicamente importante se o número racional for dado como uma razão de dois números inteiros (como ) ou na expansão decimal (como )? Em outras palavras, existe uma família de números racionais de tal modo que o tamanho da expansão decimal não seja polinomialmente limitado no tamanho da representação da razão ou o contrário?24/132.5334567¯

JS_
fonte
para digamos que você precisa precisão bits, multiplique o fornecido com em binário e aplique a iteração de newton cstheory.stackexchange.com/questions/9706/… . 2bq110000b length 
T ....

Respostas:

19

Q1 Este é um notório problema em aberto. É conhecido por estar no quarto nível da hierarquia de contagem , devido a [ABKM] . Não é conhecido por estar em NP. O problema não está na computação das raízes quadradas, conforme reivindicado nas notas da aula: bits de uma raiz quadrada de um número inteiro podem ser calculados no polinômio do tempo em e no tamanho de bits do número inteiro. O problema é, sim, quão perto a soma das raízes quadradas de números inteiros pode chegar a um número inteiro, sem realmente ser integral.nn

Q2 O caso é obviamente fácil. É o mesmo que , que está no tempo polinomial, porque o quadrado de um número racional está no tempo polinomial.n=1qA2

Q3 De acordo com esta página , o melhor que se sabe é que existem números inteiros , todos entre e , de forma que . Esse é um limite inferior de no número de bits necessários para serem computados para o problema potencialmente mais difícil que permite coeficientes negativos. O melhor limite superior do número de bits é exponencial em .a1,,ak,b1,,bk1nΩ(2klogN)k|i=1kaii=1kbi|=O(n2k+3/2)Ω(2klogn)k

Q4. Eu acho que a representação decimal pode ser bastante ineficiente. A duração do período é a ordem multiplicativa de 10 módulos do denominador, que pode ser exponencial no número de bits do denominador.

Sasho Nikolov
fonte
Portanto, um problema pode ter um PTAS enquanto sua versão de decisão não é conhecida como ? NP
Lamine
@Lamine Claro, o que um tem a ver com o outro?
Sasho Nikolov
3

Você escreveu:

Por outro lado, há este artigo de Papadimitriou: http://www.sciencedirect.com/science/article/pii/0304397577900123 dizendo que é NP-completo, o que também significa que está em NP. Embora ele não prove isso no jornal, acho que ele considera a participação no NP trivial, como geralmente ocorre com esses problemas.

Por que você simplesmente não lê o jornal, em vez de postar tais alegações sem sentido? Na página 239, Papadimitriou discute cuidadosamente esses problemas e define a variante subjacente da métrica euclidiana para sua prova.

Gamow
fonte
6
Acho que isso é melhor como comentário do que como resposta, a menos que você forneça alguns detalhes sobre como o Papadimitriou evita o problema da soma das raízes quadradas.
Sasho Nikolov