Global ETD Search

Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.

Results

Showing 1 to 15 of 15 for “"3SAT"”.

  1. Parallelization of Genetic Algorithm to Solve MAX-3SAT Problem on GPUs

    … to combinatorial optimization problems. MAX-3SAT is an example of combinatorial optimization problem which has wide range of applications as many real world problems can be translated to MAX-3SAT problem. Genetic algorithms are suitable to solve MAX-3SAT problems but usually undergo premature …

    usf Repository record for Parallelization of Genetic Algorithm to Solve MAX-3SAT Problem on GPUs (opens in a new tab)

  2. In pursuit of industrial like MAXSAT with reduced MAX-3SAT random generation

    … broad classifications of problems: Random MAX-3SAT and Industrial SAT. Random MAX-3SAT problems by randomly sampling variables with a uniform probability and randomly assigning signs to the variable, one clause at a time. Industrial MAX-SAT consists of MAX-3SAT problems as encountered in the …

    colostate Repository record for In pursuit of industrial like MAXSAT with reduced MAX-3SAT random generation (opens in a new tab)

  3. Continuous-time Quantum Algorithms: Searching and Adiabatic Computation

    … for solutions to NP-complete problems e. g. 3SAT. Even so, the best known quantum algorithms for 3SAT are considered inefficient. Soon after Grover's discovery, Farhi and Gutmann [FG96] devised a "continuous-time analogue" of quantum searching. More recently Farhi <i>et. al. </i> [FGGS00] …

    waterloo Repository record for Continuous-time Quantum Algorithms: Searching and Adiabatic Computation (opens in a new tab)

  4. Spektrale Algorithmen - Mit Eigenwerten schwierige Probleme lösen

    … leistet. Weiterhin untersuchen wir zufällige 3Sat-Formeln. Hier wollen wir mit Eigenwerten obere Schranken an die Anzahl der erfüllbaren Klauseln finden. Die gefundenen Schranken sind (in den meisten Fällen) nahezu optimal.

    qucosa-diss

  5. SAT Solver akcelerovaný pomocí GPU

    … na DPLL. Právě varianta DPLL, známa jako 3SAT-DC je kompletně převedena na GPU. Práce popisuje problémy s tímto převodem spojené, stejně jako několik optimalizací a analýz. Velkým problémem je nemožnost využít v paralelním prostředí mnohé sofistikované metody známé ze sekvenčních solverů. …

    brno-tech Repository record for SAT Solver akcelerovaný pomocí GPU (opens in a new tab)

  6. Exploring Reconfigurable Analog Hopfield and Ising Networks on the SoC FPAA

    … solved three NP-hard problems (max-cut, 3SAT, and TSP), converging to optimal or good solutions in microseconds. An Ising network is also built on the same FPAA and compared to the Hopfield network on solving small max-cut and associative memory problems. The analog Hopfield network is …

    gatech Repository record for Exploring Reconfigurable Analog Hopfield and Ising Networks on the SoC FPAA (opens in a new tab)

  7. Backdoors in Satisfiability Problems

    … to previous algorithms applied to random 3SAT, structured, and real-world instances. Our proposed algorithms improve over previous algorithms for finding backdoors in two ways. First, our algorithms often find smaller backdoors. Second, our algorithms often find a much larger number of …

    waterloo Repository record for Backdoors in Satisfiability Problems (opens in a new tab)

  8. AUTOMATIC REGISTER MACHINE: A COMPUTATION MODEL WITH AUTOMATIC FUNCTIONS AND RELATIONS AS ITS OPERATIONS

    … model and find some surprising results, such as 3SAT can be recognized in near-constant steps. Moreover, as the automatic relations used in the model are actually pre-set to be bounded, we also investigate what happens if we initially give the model a big enough "working space" instead. Finally, …

    nus Repository record for AUTOMATIC REGISTER MACHINE: A COMPUTATION MODEL WITH AUTOMATIC FUNCTIONS AND RELATIONS AS ITS OPERATIONS (opens in a new tab) Download file for AUTOMATIC REGISTER MACHINE: A COMPUTATION MODEL WITH AUTOMATIC FUNCTIONS AND RELATIONS AS ITS OPERATIONS (opens in a new tab)

  9. The INDEPENDENT SET Decision Problem is NP-complete

    … of NP-complete Problems. We intend to show that 3SAT is NP-complete and then using this fact, that IS is NP-complete.

    vcu Repository record for The INDEPENDENT SET Decision Problem is NP-complete (opens in a new tab)

  10. The complexity of constraint system games with entanglement

    … including all boolean CSPs, such as 3SAT and 3-colouring. This implies that these CSP languages remain undecidable even when not succinctly presented. Prior work of Grilo, Slofstra, and Yuen shows (via a technique called simulatable codes) that every language in MIP* has a perfect …

    waterloo Repository record for The complexity of constraint system games with entanglement (opens in a new tab)

  11. Nonuniversal entanglement level statistics in projection-driven quantum circuits and glassy dynamics in classical computation circuits

    … specifically present the formulation of #2SAT, #3SAT, and #3XORSAT formulas into planar tensor networks. We use a compression-decimation algorithm introduced by us to propagate constraints in the network before coarse-graining the boundary tensors. Iterations of these two steps gradually collapse …

    bu Repository record for Nonuniversal entanglement level statistics in projection-driven quantum circuits and glassy dynamics in classical computation circuits (opens in a new tab)

  12. Computational Complexity of Soundness Verification for Neural Networks

    … soundness for neural networks trained to solve 3SAT formulae is a &Pi;P2-complete problem and conjecture that the same hardness holds for neural networks solving other NP-complete problems. Therefore, it is unlikely that even these weaker guarantees on the performance of neural networks solving …

    wustl Repository record for Computational Complexity of Soundness Verification for Neural Networks (opens in a new tab)

  13. Solving Complex Optimization Problems with Neuromorphic VO₂-based Oscillators

    … including Graph Coloring, Max-cut, and Max-3SAT. Using sub-harmonic injection locking techniques, the solution space is binarized, achieving optimal solutions within 25 oscillation cycles. Additionally, this study explores the use of VO₂ to develop brain-inspired FitzHugh-Nagumo neurons. A …

    zurich

  14. Computational and communication complexity of geometric problems

    … is APX-hard. \end{itemize} We also define MaxRM-3SAT, a restricted version of Max3SAT, and we prove that this problem is APX-hard. This problem might be interesting in its own right.\\ In the distributed setting, we define a new model, the fixed-link model, where each processor has a position on …

    uvic Repository record for Computational and communication complexity of geometric problems (opens in a new tab)

  15. Graphical structure of unsatisfiable boolean formulae

    The presented research is an introduction and analysis of a novel graph decision problem called GraphSAT. Using the tools of topology and graph theory, this new variant builds upon the classical logic and computer science problem of boolean satisfiability k-SAT. k-SAT asks if there exists a truth …

    uiuc Repository record for Graphical structure of unsatisfiable boolean formulae (opens in a new tab)