Posso te mandar em pvt. Por que nunca publicaram? Sei lá - o paper é
citadíssimo. A prova tá correta, inclusive, e é relativamente fácil de ser
feita.
2008/10/6 Marcelo Finger <[EMAIL PROTECTED]>
> 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 <http://www.ime.usp.br/%7Emfinger>
>
_______________________________________________
Logica-l mailing list
[email protected]
http://www.dimap.ufrn.br/cgi-bin/mailman/listinfo/logica-l
