Um amigo meu me passou este post de há três dias atrás na FOM:
------------------------------------------------------------------------------------------
From: Timothy Y. Chow <[EMAIL PROTECTED]>
Date: 2008/10/2
Subject: [FOM] If "NP is not in P/poly" is barely true, then it is
unprovable
To: [EMAIL PROTECTED]
Here is a simple observation which is probably not new, but which I have
not seen explicitly written down anywhere. Thanks to Andreas Blass for
sanity-checking the argument.
Recall that P/poly is the non-uniform analogue of P: it is the class of
Boolean functions computable by polynomial-size Boolean circuits. It is
widely believed that
(*) NP is not contained in P/poly.
Conjecture (*) is a somewhat stronger conjecture than P != NP, but weaker
than the conjecture that the polynomial hierarchy does not collapse.
Suppose that (*) is indeed true, but only "barely true," i.e., there
exists some function f(n) that is just barely superpolynomial, such that
there exist Boolean circuits of size f(n) that correctly solve an
NP-complete problem. Then the promised "simple observation" is that
(*) is then unprovable.
To see this, fix some way of encoding SAT instances. Let n_0(d) be the
smallest integer n such that no Boolean circuit with n inputs and n^d
gates correctly solves every instance of SAT (of the appropriate size). If
there is no such n then n_0(d) is undefined. Then (*) asserts that n_0 is
total.
The point is that if (*) is barely true, then n_0 grows very fast. As
Andreas puts it, f(n_0(d)) > (n_0(d))^d because the left side is enough
gates to solve n_0(d)-sized instances of SAT while the right side isn't.
Then for k = g(d) (and therefore also for k not of this form with just a
minor change in the estimates) f(k) > k^(n_0^{-1}(k)). Now if f is just
barely superpolynomial, then the exponent here, n_0^{-1}(k), must be just
barely above constant, and so n_0 grows very fast. If it grows fast
enough then your favorite formal system won't be able to prove that it is
total.
Tim
_______________________________________________
FOM mailing list
--------------------------------------------------------------------------------------------------------------
Vão aqui meus comentários.
O resultado supra é um caso fraco de um resultado de S. ben David e S.
ha-Levi, num preprint (nunca publicado, mas citadíssimo) de 1992.
Basicamente o resultado de bD-HL é:
- Se PA é consistente, P<NP e P=NP são independentes de PA se e somente se
existir no modelo standard para a aritmética um algoritmo ``pertíssimo de
polinomial'' para SAT. No entanto, PA não prova que esse algoritmo resolve
todas as instâncias de SAT.
(O enunciado é meu, mas o resultado acima é equivalente ao de bd-HL.)
Vou explicar as complicações subjacentes.
A função contraexemplo para P=NP (a primeira instância n qual uma máquina
polinomial falha na solução de instâncias de SAT) cresce, nos picos, além de
qualquer função recursiva total; na verdade, cresce além do Busy Beaver
(recebemos em pvt o enunciado desse teorema, e levamos mais de um ano para
prová-lo; a prova foi checada e está publicada em da Costa-Doria-Bir). Só
que tal função é não-recursive.
Usando-se o chamado conjunto BGS (que representa recursivamente todas as
máquinas polinomiais, mas não contem, obviamente, todas elas), podemos
definir uma função contra-exemplo recursiva. Mas - provar um seu crescimento
rápido é complicado; suspeito, aliás, que tal fato adequadamente formalizado
seja indecidível em ZFC, nunca pensei muito a respeito, no entanto.
Newton e eu usamos então um truque: se você fala em máquina polinomial, isto
significa que tal máquina tem um bound polinomial. Pode ser x^2 ou
x^2,000,000 não importa. Para definir todas as máquinas polinomiais, bastar
definir uma sequência infinita de bounds - apertadinhos ou largos, sem
problemas. Foi a idéia que levou à definição exótica, que, logo percebemos,
era algo muito geral.
Com ela podemos `revelar,' como numa fotografia, e facilmente, o crescimento
rápido desejado.
---------------
O raciocínio de bD-HL mostra então que o inverso da função que `envolve' os
picos da contraexemplo serve como bound para um algoritmo eficiente para
todo o SAT. Mas sem que PA, ZFC, e toda uma fieira de sistemas fortes além
de ZFC, - muito além do jardim... - possam provar (ou desprovar) isso...
_______________________________________________
Logica-l mailing list
[email protected]
http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
