Dória.
E por que Ben David e Ha Levi nunca publicaram este resultado?
Eles têm uma prova aceitável para este resultado? Como consultar tal paper?
[]s
Marcelo
2008/10/6 Francisco Antonio Doria <[EMAIL PROTECTED]>:
> 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
>
>
--
Marcelo Finger
Departamento de Ciencia da Computacao
Instituto de Matematica e Estatistica
Universidade de Sao Paulo
Rua do Matao, 1010
05508-090 Sao Paulo, SP Brazil
Tel: +55 11 3091-9688, 3091-6135, 3091-6134 (fax)
http://www.ime.usp.br/~mfinger
_______________________________________________
Logica-l mailing list
[email protected]
http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
