skip to main content
Idioma:
Primo Search
Clear Search Box
Search in: Busca Geral
Busca Avançada
Busca por Índices
Tipo de recurso Mostra resultados com: Mostra resultados com: Índice

A characterization of tree-like Resolution size

Beyersdorff, Olaf ; Galesi, Nicola ; Lauria, Massimo

Information processing letters, 2013-09, Vol.113 (18), p.666-671 [Periódico revisado por pares]

Amsterdam: Elsevier B.V

Texto completo disponível

Citações Citado por
  • Título:
    A characterization of tree-like Resolution size
  • Autor: Beyersdorff, Olaf ; Galesi, Nicola ; Lauria, Massimo
  • Assuntos: Asymmetry ; Complexity ; Computational complexity ; Data processing ; Game theory ; Games ; Information theory ; Lower bounds ; Optimization ; Proof complexity ; Proof theory ; Prover-Delayer games ; Proving ; Resolution ; Studies
  • É parte de: Information processing letters, 2013-09, Vol.113 (18), p.666-671
  • Notas: ObjectType-Article-2
    SourceType-Scholarly Journals-1
    ObjectType-Feature-1
    content type line 23
  • Descrição: We explain an asymmetric Prover–Delayer game which precisely characterizes proof size in tree-like Resolution. This game was previously described in a parameterized complexity context to show lower bounds for parameterized formulas (Beyersdorff et al. (2013) [2]) and for the classical pigeonhole principle (Beyersdorff et al. (2010) [1]). The main point of this note is to show that the asymmetric game in fact characterizes tree-like Resolution proof size, i.e. in principle our proof method allows to always achieve the optimal lower bounds. This is in contrast with previous techniques described in the literature. We also provide a very intuitive information-theoretic interpretation of the game. •We explain an asymmetric Prover–Delayer game which precisely characterizes proof size in tree-like Resolution.•Our proof method allows to always achieve the optimal lower bounds.•Intuitive information-theoretic interpretation of the game.
  • Editor: Amsterdam: Elsevier B.V
  • Idioma: Inglês
Links
Voltar para lista de resultados

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.