Sökning: "Proof complexity"

Visar resultat 1 - 5 av 41 avhandlingar innehållade orden Proof complexity.

  1. 1. Space in Proof Complexity

    Detta är en avhandling från Stockholm : KTH Royal Institute of Technology

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

    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

  2. 2. On Some Combinatorial Optimization Problems Algorithms and Complexity

    Detta är en avhandling från Linköping : Linköping University Electronic Press

    Författare :Hannes Uppman; Linköpings universitet.; Linköpings universitet.; [2015]
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Computational complexity; optimization; constraint satisfaction problem;

    Sammanfattning : 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). LÄS MER

  3. 3. Short Proofs May Be Spacious Understanding Space in Resolution

    Detta är en avhandling från Stockholm : KTH

    Författare :Jakob Nordström; KTH.; [2008]
    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; MATHEMATICS Applied mathematics Theoretical computer science; MATEMATIK Tillämpad matematik 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

  4. 4. On Complexity Measures in Polynomial Calculus

    Detta är en avhandling från Stockholm, Sweden : KTH Royal Institute of Technology

    Författare :Mladen Mikša; KTH.; [2016]
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Datalogi; Computer Science;

    Sammanfattning : Proof complexity is the study of different resources that a proof needs in different proof systems for propositional logic. This line of inquiry relates to the fundamental questions in theoretical computer science, as lower bounds on proof size for an arbitrary proof system would separate P from NP. LÄS MER

  5. 5. Functional Program Correctness Through Types

    Detta är en avhandling från Chalmers University of Technology

    Författare :Nils Anders Danielsson; Chalmers tekniska högskola.; Chalmers University of Technology.; [2007]
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Datalogi; Computer science; program correctness; total languages; partial languages; time complexity; lazy evaluation; dependent types; strong invariants; well-typed syntax; normalisation by evaluation;

    Sammanfattning : This thesis addresses the problem of avoiding errors in functional programs. The thesis has three parts, discussing different aspects of program correctness, with the unifying theme that types are an integral part of the methods used to establish correctness. LÄS MER