Sökning: "pebble game"

Hittade 2 avhandlingar innehållade orden pebble game.

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. Space in Proof Complexity

   Författare :Marc Vinyals; Jakob Nordström; Yehudayoff Amir; KTH; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; proof complexity; resolution; polynomial calculus; cutting planes; space complexity; computational complexity; pebble games; communication complexity; CDCL; Computer Science; Datalogi;

   Sammanfattning : ropositional proof complexity is the study of the resources that are needed to prove formulas in propositional logic. In this thesis we are concerned with the size and space of proofs, and in particular with the latter.Different approaches to reasoning are captured by corresponding proof systems. LÄS MER