Search for dissertations about: "proof complexity"

Showing result 1 - 5 of 65 swedish dissertations containing the words proof complexity.

  2. 1. Space in Proof Complexity

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

    Abstract : 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. READ MORE

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

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

    Abstract : 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. READ MORE

  5. 3. On Some Combinatorial Optimization Problems : Algorithms and Complexity

    Author : Hannes Uppman; Peter Jonsson; Christer Bäckström; Ulf Nilsson; Stanislav Živný; Linköpings universitet; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; Computational complexity; optimization; constraint satisfaction problem;

    Abstract : This thesis is about the computational complexity of several classes of combinatorial optimization problems, all related to the constraint satisfaction problems.A constraint language consists of a domain and a set of relations on the domain. For each such language there is a constraint satisfaction problem (CSP). READ MORE

  6. 4. On Long Proofs of Simple Truths

    Author : Kilian Risse; Per Austrin; Johan Håstad; Jakob Nordström; Benjamin Rossman; KTH; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; Computational Complexity; Lower Bounds; Proof Complexity; Datalogi; Computer Science;

    Abstract : Propositional proof complexity is the study of certificates of infeasibility. In this thesis we consider several proof systems with limited deductive ability and unconditionally show that they require long refutations of the feasibility of certain Boolean formulas. READ MORE

  7. 5. Short Proofs May Be Spacious : Understanding Space in Resolution

    Author : Jakob Nordström; Johan Håstad; Albert Atserias; KTH; []
    Keywords : 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;

    Abstract : 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. READ MORE