Sökning: "k-SAT"

Hittade 3 avhandlingar innehållade ordet k-SAT.

  1. 1. On random satisfiability and optimization problems

    Författare :Joel Larsson; Klas Markström; Roland Häggkvist; Victor Falgas Ravry; Stefanie Gerke; Umeå universitet; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Random graphs; k-SAT; satisfiability; coupon collector; random cover time; threshold phenomenon; concentration of measure; combinatorial probability; perfect matching; assignment problem; local graph limit; mean-field; Mathematics; matematik;

    Sammanfattning : In Paper I, we study the following optimization problem: in the complete bipartite graph where edges are given i.i.d. weights of pseudo-dimension q>0, find a perfect matching with minimal total weight. LÄS MER

  3. 2. On state space structure and average case complexity in random K-SAT problems

    Författare :John Ardelius; Erik Aurell; Bart Selman; KTH; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Computer science; Datavetenskap;

    Sammanfattning : This thesis gives an introduction to a currently active area in the cross-section between theoretical computer science and theoretical physics. In the last ten years it has been suggested that critical behaviour, usually seen in models from condensed matter physics, may be responsible for the intractability of NP complete computation problems. LÄS MER

  4. 3. On random cover and matching problems

    Författare :Joel Larsson; Klas Markström; Tatyana Turova; Umeå universitet; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Mathematics; matematik;

    Sammanfattning : This thesis consists of the following papers.I  J. Larsson, The Minimum Matching in Pseudo-dimension 0 < q < 1, submittedII  V. Falgas-Ravry, J. LÄS MER