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

Parameterized Complexity of DPLL Search Procedures

Beyersdorff, Olaf ; Galesi, Nicola ; Lauria, Massimo

ACM transactions on computational logic, 2013-08, Vol.14 (3), p.1-21 [Periódico revisado por pares]

ACM

Texto completo disponível

Citações Citado por
  • Título:
    Parameterized Complexity of DPLL Search Procedures
  • Autor: Beyersdorff, Olaf ; Galesi, Nicola ; Lauria, Massimo
  • Assuntos: Algorithms ; Combinatorial analysis ; Complexity ; Games ; Graphs ; Lower bounds ; Mathematical models ; parameterized complexity ; Proof complexity ; prover-delayer games ; resolution ; Running ; Theory
  • É parte de: ACM transactions on computational logic, 2013-08, Vol.14 (3), p.1-21
  • Notas: ObjectType-Article-1
    SourceType-Scholarly Journals-1
    ObjectType-Feature-2
    content type line 23
  • Descrição: We study the performance of DPLL algorithms on parameterized problems. In particular, we investigate how difficult it is to decide whether small solutions exist for satisfiability and other combinatorial problems. For this purpose we develop a Prover-Delayer game that models the running time of DPLL procedures and we establish an information-theoretic method to obtain lower bounds to the running time of parameterized DPLL procedures. We illustrate this technique by showing lower bounds to the parameterized pigeonhole principle and to the ordering principle. As our main application we study the DPLL procedure for the problem of deciding whether a graph has a small clique. We show that proving the absence of a k -clique requires n Ω(k) steps for a nontrivial distribution of graphs close to the critical threshold. For the restricted case of tree-like Parameterized Resolution, this result answers a question asked by Beyersdorff et al. [2012] of understanding the Resolution complexity of this family of formulas.
  • Editor: ACM
  • 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.