Eu tenho lido um pouco sobre o método da soma dos quadrados (SOS) da pesquisa de Barak & Steurer e das notas de aula de Barak . Nos dois casos, eles varrem questões de precisão numérica para baixo do tapete.
Do meu entendimento (reconhecidamente limitado) do método, o seguinte deve ser verdadeiro:
Dado qualquer sistema de igualdades polinomiais sobre variáveis de valor real x ∈ R n , em que todos os parâmetros são O ( 1 ) ( n , | E | e grau de cada restrição), o grau- " 2 n " ( = O ( 1 ) ) O método SOS encontra uma atribuição satisfatória das variáveis ou prova que não existe no tempo O ( 1 ) .
Minha primeira pergunta é se a afirmação acima é verdadeira (existe um argumento ingênuo que não usa o SOS para resolver isso?). A segunda pergunta é onde a precisão numérica se encaixa. Se eu quiser obter uma atribuição que satisfaça todas as restrições com precisão aditiva , como o tempo de execução depende de 1 / ε ? Em particular, é polinomial?
A motivação para isso é, por exemplo, aplicar uma abordagem de dividir e conquistar em um sistema grande até que o caso base seja um sistema de tamanho .
EDIT: De Barak-Steurer, parece que o " algoritmo da soma dos quadrados em graus " na p.9 (e os parágrafos anteriores) definem problemas para soluções em vez de R e, de fato, a definição de um pseudo -Distribuição na seção 2.2 é mais de R . Agora estou vendo no Lema 2.2, no entanto, que não é garantida uma solução / refutação no grau 2 n sem variáveis binárias.
Para refinar minha pergunta um pouco. Se suas variáveis não são binárias, a preocupação é que a sequência de saídas não seja finita (talvez nem mesmo monotônica aumente?). Portanto, a questão é: φ ( l ) ainda está aumentando? E se sim, até que ponto você precisa ir para obter a precisão aditiva ε ?
Embora isso provavelmente não muda nada, acontece que eu sei que meu sistema é satisfiable (não há refutação de qualquer grau), então eu realmente estou apenas preocupado com o quão grande precisa ser. Finalmente, estou interessado em uma solução teórica, não em um solucionador numérico.
fonte
Respostas:
Aqui está o comentário de Boaz Barak sobre o assunto:
fonte
Acho que minha resposta provavelmente é insuficiente, mas permanece por uma questão de integridade (embora veja os comentários de Boaz abaixo para provavelmente uma resposta melhor)
Quando nos limitamos a variáveis booleanas, a afirmação pode ser vista quando para todos i ∈ [ n ] com a observação de que as pseudo-distribuições de grau 2 n são distribuições reais, ou seja, suponha que você tenha uma pseudo-distribuição μ ( x ) sobre as soluções x das suas igualdades polinomiais E satisfazendo:(x2i−1)∈E i∈[n] 2n μ(x) x E
e ∑ x ∈ { - 1 , 1 } n μ ( x ) p 2 ( x ) ≥ 0 para todos os polinômios p com grau no máximo n∑x∈{−1,1}nμ(x) ∑x∈{−1,1}nμ(x)p2(x)≥0 p n
Mas os polinômios de grau incluem o polinômio indicador (por exemplo, x 1 = 1 , x 2 = - 1 , x 3 = 1 possui 2 - 3 ( 1 + x 1 ) ( 1 - x 2 ) ( 1 + x 3 ) que é zero em qualquer outro lugar e 1 nessa atribuição). Então μ ( x ) ≥ 0 para todos x ∈ {n x1=1,x2=−1,x3=1 2−3(1+x1)(1−x2)(1+x3) μ(x)≥0 , portanto, concluir μ é uma distribuição efectiva sobre as soluções de E . Grau l pseudo-distribuições podem ser encontrados através da utilização de programação semidefinido para encontrar um grau associado ℓ operador pseudo-expectativa em n ó ( ℓ ) tempo, de modo que podemos encontrar a distribuição real μ no tempo N O ( n ) através da utilização desse pseudo expectativa (agora uma expectativa real) de encontrar todos os momentos de μ .x∈{−1,1}n μ E ℓ ℓ nO(ℓ) μ nO(n) μ
Então se , você pode encontrar uma distribuição de soluções para E no tempo de O ( 1 ) . Obviamente, a busca por força bruta garante o mesmo.|E|=O(1) E O(1)
No entanto, se as soluções não forem necessariamente booleanas, as pseudo-expectativas de grau não serão suficientes para encontrar uma distribuição entre as soluções. Como pode ser visto acima, a prova de que as pseudo-distribuições do grau 2 n são distribuições reais depende do fato de que os polinômios do grau n são suficientes para 'selecionar' as atribuições individuais, o que não é verdade de maneira mais geral. Outra maneira de ver é que polinômios de variável booleana são considerados2n 2n n , então o grau de todo monômio é no máximo n .mod(x2i) n
Por exemplo, pode-se considerar a substituição de cada variável binária com uma variável 4-ário, digamos, incluindo . Então você teria que ter uma pseudo-expectativa de grau 4 n para garantir a recuperação de uma distribuição sobre soluções.(x2i−1)(x2i−4)∈E 4n
Agora, para garantias teóricas, parece que aproximar a raiz de um sistema de polinomal também é conhecido como o 17º problema de Smale e, aparentemente, existe um algoritmo de tempo polinomial aleatório (Las Vegas) que resolve isso - veja http://arxiv.org /pdf/1211.1528v1.pdf . Observe que isso parece estar no modelo Blum-Shub-Smale, portanto, as operações reais são as primitivas. Não tenho certeza se isso dá a garantia de que você precisa.
fonte