Sökning: "pebbling formula"

Hittade 2 avhandlingar innehållade orden pebbling formula.

1. 1. Short Proofs May Be Spacious : Understanding Space in Resolution

   Författare :Jakob Nordström; Johan Håstad; Albert Atserias; KTH; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Proof complexity; resolution; space; length; width; separation; lower bound; pebble game; pebbling formula; Beviskomplexitet; resolution; minne; längd; bredd; separation; undre gräns; pebblingspel; pebblingformel; Theoretical computer science; Teoretisk datalogi;

   Sammanfattning : Om man ser på de bästa nu kända algoritmerna för att avgöra satisfierbarhet hos logiska formler så är de allra flesta baserade på den så kallade DPLL-metoden utökad med klausulinlärning. De två viktigaste gränssättande faktorerna för sådana algoritmer är hur mycket tid och minne de använder, och att förstå sig på detta är därför en fråga som har stor praktisk betydelse. LÄS MER

3. 2. Lower Bounds and Trade-offs in Proof Complexity

   Författare :Susanna F. de Rezende; Jakob Nordström; Amit Chakrabarti; KTH; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Proof complexity; trade-offs; lower bounds; size; length; space; Computer Science; Datalogi;

   Sammanfattning : Propositional proof complexity is a field in theoretical computer science that analyses the resources needed to prove statements. In this thesis, we are concerned about the length of proofs and trade-offs between different resources, such as length and space. LÄS MER