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 .√
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?
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 √ Akp(tamanho da entrada)
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:
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?
Respostas:
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.n n
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=1 q≤A2
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,…,bk 1 n Ω(2klogN)k|∑ki=1ai−−√−∑ki=1bi−−√|=O(n−2k+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.
fonte
Você escreveu:
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.
fonte