Sökning: "satisfiability"

Visar resultat 1 - 5 av 39 avhandlingar innehållade ordet satisfiability.

1. 1. Exact Algorithms for Exact Satisfiability Problems

   Författare :Vilhelm Dahllöf; Peter Jonsson; Fedor Fomin; Linköpings universitet; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; NP-hardness; exact algorithms; satisfiability; exact satisfiability; Computer science; Datalogi;

   Sammanfattning : This thesis presents exact means to solve a family of NP-hard problems. Starting with the well-studied Exact Satisfiability problem (XSAT) parents, siblings and daughters are derived and studied, each with interesting practical and theoretical properties. LÄS MER

3. 2. 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

4. 3. Algorithms, measures and upper bounds for satisfiability and related problems

   Författare :Magnus Wahlström; Peter Jonsson; Oliver Kullmann; Linköpings universitet; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Exact algorithms; upper bounds; algorithm analysis; satisfiability; Computer science; Datavetenskap;

   Sammanfattning : The topic of exact, exponential-time algorithms for NP-hard problems has received a lot of attention, particularly with the focus of producing algorithms with stronger theoretical guarantees, e.g. upper bounds on the running time on the form O(c^n) for some c. LÄS MER

5. 4. Label Cover Reductions for Unconditional Approximation Hardness of Constraint Satisfaction

   Författare :Cenny Wenner; Johan Håstad; Irit Dinur; Numerical Analysis and Computer Science (NADA) Faculty of Science Stockholm University; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Optimization; NP; Approximation; Approximability; Inapproximability; Constraint Satisfaction; CSP; Boolean Analysis; Satisfiability; SAT; Acyclic Subgraph; Betweenness; Unique Games; Computer Science; Datalogi;

   Sammanfattning : Problem solving is an integral aspect of modern society and includes such tasks as picking the fastest route to work, optimizing a production line, scheduling computer tasks, placing new bus stops, or picking a meal from available ingredients.We study the hardness of solving Constraint Satisfaction Problems (CSPs). LÄS MER

7. 5. Using Formal Methods for Product and Production Development -- Industrial Applications for Boolean Satisfiability Solvers

   Författare :Alexey Voronov; Chalmers tekniska högskola; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; NATURVETENSKAP; NATURAL SCIENCES; Formal Methods; Industrial Automation; Boolean Satisfiability; Product and Production Development;

   Sammanfattning : Highly customized products and frequent changes in the production systems pose high demands on engineers. The amount of data and the complexity of the relations within the data are high. Thus, it is both error-prone and time consuming to analyze the data without software support. LÄS MER