Log in

Relevant bibliographies by topics / 3-Satisfiability / Journal articles

To see the other types of publications on this topic, follow the link: 3-Satisfiability.

Journal articles on the topic '3-Satisfiability'

Author: Grafiati

Published: 4 June 2021

Last updated: 1 February 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic '3-Satisfiability.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Bazuhair, Muna Mohammed, Siti Zulaikha Mohd Jamaludin, Nur Ezlin Zamri, Mohd Shareduwan Mohd Kasihmuddin, Mohd Asyraf Mansor, Alyaa Alway, and Syed Anayet Karim. "Novel Hopfield Neural Network Model with Election Algorithm for Random 3 Satisfiability." Processes 9, no. 8 (July 26, 2021): 1292. http://dx.doi.org/10.3390/pr9081292.

Full text

Abstract:

One of the influential models in the artificial neural network (ANN) research field for addressing the issue of knowledge in the non-systematic logical rule is Random k Satisfiability. In this context, knowledge structure representation is also the potential application of Random k Satisfiability. Despite many attempts to represent logical rules in a non-systematic structure, previous studies have failed to consider higher-order logical rules. As the amount of information in the logical rule increases, the proposed network is unable to proceed to the retrieval phase, where the behavior of the Random Satisfiability can be observed. This study approaches these issues by proposing higher-order Random k Satisfiability for k ≤ 3 in the Hopfield Neural Network (HNN). In this regard, introducing the 3 Satisfiability logical rule to the existing network increases the synaptic weight dimensions in Lyapunov’s energy function and local field. In this study, we proposed an Election Algorithm (EA) to optimize the learning phase of HNN to compensate for the high computational complexity during the learning phase. This research extensively evaluates the proposed model using various performance metrics. The main findings of this research indicated the compatibility and performance of Random 3 Satisfiability logical representation during the learning and retrieval phase via EA with HNN in terms of error evaluations, energy analysis, similarity indices, and variability measures. The results also emphasized that the proposed Random 3 Satisfiability representation incorporates with EA in HNN is capable to optimize the learning and retrieval phase as compared to the conventional model, which deployed Exhaustive Search (ES).

APA, Harvard, Vancouver, ISO, and other styles

2

Gorbenko, A., and V. Popov. "Coevolving solutions of the 3-satisfiability problem." Applied Mathematical Sciences 7 (2013): 603–8. http://dx.doi.org/10.12988/ams.2013.13051.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Seitz, Sakari, Mikko Alava, and Pekka Orponen. "Focused local search for random 3-satisfiability." Journal of Statistical Mechanics: Theory and Experiment 2005, no. 06 (June 14, 2005): P06006. http://dx.doi.org/10.1088/1742-5468/2005/06/p06006.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

PITTEL, BORIS, and GREGORY B. SORKIN. "The Satisfiability Threshold fork-XORSAT." Combinatorics, Probability and Computing 25, no. 2 (July 31, 2015): 236–68. http://dx.doi.org/10.1017/s0963548315000097.

Full text

Abstract:

We consider ‘unconstrained’ randomk-XORSAT, which is a uniformly random system ofmlinear non-homogeneous equations in$\mathbb{F}$2overnvariables, each equation containingk⩾ 3 variables, and also consider a ‘constrained’ model where every variable appears in at least two equations. Dubois and Mandler proved thatm/n= 1 is a sharp threshold for satisfiability of constrained 3-XORSAT, and analysed the 2-core of a random 3-uniform hypergraph to extend this result to find the threshold for unconstrained 3-XORSAT.We show thatm/n= 1 remains a sharp threshold for satisfiability of constrainedk-XORSAT for everyk⩾ 3, and we use standard results on the 2-core of a randomk-uniform hypergraph to extend this result to find the threshold for unconstrainedk-XORSAT. For constrainedk-XORSAT we narrow the phase transition window, showing thatm − n→ −∞ implies almost-sure satisfiability, whilem − n→ +∞ implies almost-sure unsatisfiability.

APA, Harvard, Vancouver, ISO, and other styles

5

Mansor, Mohd Asyraf, and Saratha Sathasivam. "Accelerating Activation Function for 3- Satisfiability Logic Programming." International Journal of Intelligent Systems and Applications 8, no. 10 (October 8, 2016): 44–50. http://dx.doi.org/10.5815/ijisa.2016.10.05.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Billionnet, Alain, and Alain Sutter. "An efficient algorithm for the 3-satisfiability problem." Operations Research Letters 12, no. 1 (July 1992): 29–36. http://dx.doi.org/10.1016/0167-6377(92)90019-y.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Seitz, Sakari, and Pekka Orponen. "An efficient local search method for random 3-satisfiability." Electronic Notes in Discrete Mathematics 16 (October 2003): 71–79. http://dx.doi.org/10.1016/s1571-0653(04)00463-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Porschen, Stefan, Bert Randerath, and Ewald Speckenmeyer. "Exact 3-Satisfiability Is Decidable in Time O(20.16254n )." Annals of Mathematics and Artificial Intelligence 43, no. 1-4 (January 2005): 173–93. http://dx.doi.org/10.1007/s10472-004-9428-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Porschen, Stefan, Bert Randerath, and Ewald Speckenmeyer. "Exact 3-satisfiability is decidable in time O(20.16254n )." Annals of Mathematics and Artificial Intelligence 43, no. 1-4 (December 31, 2004): 173–93. http://dx.doi.org/10.1007/s10472-005-0428-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

De Ita Luna, Guillermo, Cristina López Ramírez, and Meliza González Contreras. "Modelling 3-Coloring of Outerplanar Graphs via Incremental Satisfiability." Electronic Notes in Discrete Mathematics 69 (August 2018): 101–8. http://dx.doi.org/10.1016/j.endm.2018.07.014.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

Johnson, James L. "A neural network approach to the 3-satisfiability problem." Journal of Parallel and Distributed Computing 6, no. 2 (April 1989): 435–49. http://dx.doi.org/10.1016/0743-7315(89)90068-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

Mohd Jamaludin, Siti Zulaikha, Mohd Shareduwan Mohd Kasihmuddin, Ahmad Izani Md Ismail, Mohd Asyraf Mansor, and Md Faisal Md Basir. "Energy Based Logic Mining Analysis with Hopfield Neural Network for Recruitment Evaluation." Entropy 23, no. 1 (December 30, 2020): 40. http://dx.doi.org/10.3390/e23010040.

Full text

Abstract:

An effective recruitment evaluation plays an important role in the success of companies, industries and institutions. In order to obtain insight on the relationship between factors contributing to systematic recruitment, the artificial neural network and logic mining approach can be adopted as a data extraction model. In this work, an energy based k satisfiability reverse analysis incorporating a Hopfield neural network is proposed to extract the relationship between the factors in an electronic (E) recruitment data set. The attributes of E recruitment data set are represented in the form of k satisfiability logical representation. We proposed the logical representation to 2-satisfiability and 3-satisfiability representation, which are regarded as a systematic logical representation. The E recruitment data set is obtained from an insurance agency in Malaysia, with the aim of extracting the relationship of dominant attributes that contribute to positive recruitment among the potential candidates. Thus, our approach is evaluated according to correctness, robustness and accuracy of the induced logic obtained, corresponding to the E recruitment data. According to the experimental simulations with different number of neurons, the findings indicated the effectiveness and robustness of energy based k satisfiability reverse analysis with Hopfield neural network in extracting the dominant attributes toward positive recruitment in the insurance agency in Malaysia.

APA, Harvard, Vancouver, ISO, and other styles

13

BARRETT, CLARK, MORGAN DETERS, ALBERT OLIVERAS, and AARON STUMP. "DESIGN AND RESULTS OF THE 3RD ANNUAL SATISFIABILITY MODULO THEORIES COMPETITION (SMT-COMP 2007)." International Journal on Artificial Intelligence Tools 17, no. 04 (August 2008): 569–606. http://dx.doi.org/10.1142/s0218213008004060.

Full text

Abstract:

The Satisfiability Modulo Theories Competition (SMT-COMP) is an annual competition aimed at stimulating the advance of the state-of-the-art techniques and tools developed by the Satisfiability Modulo Theories (SMT) community. As with the first two editions, SMT-COMP 2007 was held as a satellite event of CAV 2007, held July 3-7, 2007. This paper gives an overview of the rules, competition format, benchmarks, participants and results of SMT-COMP 2007.

APA, Harvard, Vancouver, ISO, and other styles

14

PRATT-HARTMANN, IAN, WIESŁAW SZWAST, and LIDIA TENDERA. "THE FLUTED FRAGMENT REVISITED." Journal of Symbolic Logic 84, no. 3 (June 6, 2019): 1020–48. http://dx.doi.org/10.1017/jsl.2019.33.

Full text

Abstract:

AbstractWe study the fluted fragment, a decidable fragment of first-order logic with an unbounded number of variables, motivated by the work of W. V. Quine. We show that the satisfiability problem for this fragment has nonelementary complexity, thus refuting an earlier published claim by W. C. Purdy that it is in NExpTime. More precisely, we consider ${\cal F}{{\cal L}^m}$, the intersection of the fluted fragment and the m-variable fragment of first-order logic, for all $m \ge 1$. We show that, for $m \ge 2$, this subfragment forces $\left\lfloor {m/2} \right\rfloor$-tuply exponentially large models, and that its satisfiability problem is $\left\lfloor {m/2} \right\rfloor$-NExpTime-hard. We further establish that, for $m \ge 3$, any satisfiable ${\cal F}{{\cal L}^m}$-formula has a model of at most ($m - 2$)-tuply exponential size, whence the satisfiability (= finite satisfiability) problem for this fragment is in ($m - 2$)-NExpTime. Together with other, known, complexity results, this provides tight complexity bounds for ${\cal F}{{\cal L}^m}$ for all $m \le 4$.

APA, Harvard, Vancouver, ISO, and other styles

15

Chao, Ming-Te, and John Franco. "Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem." SIAM Journal on Computing 15, no. 4 (November 1986): 1106–18. http://dx.doi.org/10.1137/0215080.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Popov, Vladimir. "A genetic algorithm with expansion operator for the 3-satisfiability problem." Advanced Studies in Theoretical Physics 7 (2013): 359–61. http://dx.doi.org/10.12988/astp.2013.13035.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Goemans, Michel X., and David P. Williamson. "New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem." SIAM Journal on Discrete Mathematics 7, no. 4 (November 1994): 656–66. http://dx.doi.org/10.1137/s0895480192243516.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Lopez Ramirez, Cristina, and Guillermo De Ita Luna. "Modelling the 3-coloring of Serial-Parallel Graphs via Incremental Satisfiability." IEEE Latin America Transactions 17, no. 04 (April 2019): 607–14. http://dx.doi.org/10.1109/tla.2019.8891885.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Luo, Chuan, Kaile Su, and Shaowei Cai. "More efficient two-mode stochastic local search for random 3-satisfiability." Applied Intelligence 41, no. 3 (June 22, 2014): 665–80. http://dx.doi.org/10.1007/s10489-014-0556-7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Kulikov, A. S. "An upper bound O(20.16254n) for exact 3-satisfiability: a simpler proof." Journal of Mathematical Sciences 126, no. 3 (March 2005): 1195–99. http://dx.doi.org/10.1007/s10958-005-0096-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Lin, Qingwen, Xiaofeng Wang, and Jin Niu. "A New Method for 3-Satisfiability Problem Phase Transition on Structural Entropy." IEEE Access 9 (2021): 2093–99. http://dx.doi.org/10.1109/access.2020.3047930.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Cocco, Simona, and Rémi Monasson. "Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances." Theoretical Computer Science 320, no. 2-3 (June 2004): 345–72. http://dx.doi.org/10.1016/j.tcs.2004.02.034.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Maneva, Elitza, and Alistair Sinclair. "On the satisfiability threshold and clustering of solutions of random 3-SAT formulas." Theoretical Computer Science 407, no. 1-3 (November 2008): 359–69. http://dx.doi.org/10.1016/j.tcs.2008.06.053.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Mansor, Mohd Asyraf, Mohd Shareduwan Mohd Kasihmuddin, and Saratha Sathasivam. "Grey Wolf Optimization algorithm with Discrete Hopfield Neural Network for 3 Satisfiability analysis." Journal of Physics: Conference Series 1821, no. 1 (March 1, 2021): 012038. http://dx.doi.org/10.1088/1742-6596/1821/1/012038.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Nakajima, T., and A. Suyama. "A new architecture of DNA computer and calculating a 3-satisfiability problem with it." Seibutsu Butsuri 41, supplement (2001): S87. http://dx.doi.org/10.2142/biophys.41.s87_3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Darmann, Andreas, Janosch Döcker, and Britta Dorn. "The Monotone Satisfiability Problem with Bounded Variable Appearances." International Journal of Foundations of Computer Science 29, no. 06 (September 2018): 979–93. http://dx.doi.org/10.1142/s0129054118500168.

Full text

Abstract:

The prominent Boolean formula satisfiability problem SAT is known to be [Formula: see text]-complete even for very restricted variants such as 3-SAT, Monotone 3-SAT, or Planar 3-SAT, or instances with bounded variable appearance. We settle the computational complexity status for two variants with bounded variable appearance: We show that Planar Monotone Sat — the variant of Monotone Sat in which the incidence graph is required to be planar — is [Formula: see text]-complete even if each clause consists of at most three distinct literals and each variable appears exactly three times, and that Monotone Sat is [Formula: see text]-complete even if each clause consists of three distinct literals and each variable appears exactly four times in the formula. The latter confirms a conjecture stated in scribe notes [7] of an MIT lecture by Eric Demaine. In addition, we provide hardness results with respect to bounded variable appearances for two variants of Planar Monotone Sat.

APA, Harvard, Vancouver, ISO, and other styles

27

Cameron, Chris, Rex Chen, Jason Hartford, and Kevin Leyton-Brown. "Predicting Propositional Satisfiability via End-to-End Learning." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 04 (April 3, 2020): 3324–31. http://dx.doi.org/10.1609/aaai.v34i04.5733.

Full text

Abstract:

Strangely enough, it is possible to use machine learning models to predict the satisfiability status of hard SAT problems with accuracy considerably higher than random guessing. Existing methods have relied on extensive, manual feature engineering and computationally complex features (e.g., based on linear programming relaxations). We show for the first time that even better performance can be achieved by end-to-end learning methods — i.e., models that map directly from raw problem inputs to predictions and take only linear time to evaluate. Our work leverages deep network models which capture a key invariance exhibited by SAT problems: satisfiability status is unaffected by reordering variables and clauses. We showed that end-to-end learning with deep networks can outperform previous work on random 3-SAT problems at the solubility phase transition, where: (1) exactly 50% of problems are satisfiable; and (2) empirical runtimes of known solution methods scale exponentially with problem size (e.g., we achieved 84% prediction accuracy on 600-variable problems, which take hours to solve with state-of-the-art methods). We also showed that deep networks can generalize across problem sizes (e.g., a network trained only on 100-variable problems, which typically take about 10 ms to solve, achieved 81% accuracy on 600-variable problems).

APA, Harvard, Vancouver, ISO, and other styles

28

Kathirvel, Vigneshwer, Mohd Asyraf Mansor, Mohd Shareduwan Mohd Kasihmuddin, and Saratha Sathasivam. "Hybrid Imperialistic Competitive Algorithm Incorporated with Hopfield Neural Network for Robust 3 Satisfiability Logic Programming." IAES International Journal of Artificial Intelligence (IJ-AI) 8, no. 2 (June 1, 2019): 144. http://dx.doi.org/10.11591/ijai.v8.i2.pp144-155.

Full text

Abstract:

Imperialist Competitive algorithm (ICA) is a robust training algorithm inspired by the socio-politically motivated strategy. This paper focuses on utilizing a hybridized ICA with Hopfield Neural Network on a 3-Satisfiability (3-SAT) logic programming. Eventually the performance of the proposed algorithm will be compared to other 2 algorithms, which are HNN-3SATES (ES) and HNN-3SATGA (GA). The performance shall be evaluated with the Root Mean Square Error (RMSE), Mean Absolute Error (MAE), Sum of Squares Error (SSE), Schwarz Bayesian Criterion (SBC), Global Minima Ratio and Computation Time (CPU time). The expected outcome will portray that the IC algorithm will outperform the other two algorithms in doing 3-SAT logic programming.

APA, Harvard, Vancouver, ISO, and other styles

29

van Maaren, Hans, and Linda van Norden. "Correlations between Horn fractions, satisfiability and solver performance for fixed density random 3-CNF instances." Annals of Mathematics and Artificial Intelligence 44, no. 1-2 (May 2005): 157–77. http://dx.doi.org/10.1007/s10472-005-2369-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Singer, J., I. P. Gent, and A. Smaill. "Backbone Fragility and the Local Search Cost Peak." Journal of Artificial Intelligence Research 12 (May 1, 2000): 235–70. http://dx.doi.org/10.1613/jair.711.

Full text

Abstract:

The local search algorithm WSat is one of the most successful algorithms for solving the satisfiability (SAT) problem. It is notably effective at solving hard Random 3-SAT instances near the so-called `satisfiability threshold', but still shows a peak in search cost near the threshold and large variations in cost over different instances. We make a number of significant contributions to the analysis of WSat on high-cost random instances, using the recently-introduced concept of the backbone of a SAT instance. The backbone is the set of literals which are entailed by an instance. We find that the number of solutions predicts the cost well for small-backbone instances but is much less relevant for the large-backbone instances which appear near the threshold and dominate in the overconstrained region. We show a very strong correlation between search cost and the Hamming distance to the nearest solution early in WSat's search. This pattern leads us to introduce a measure of the backbone fragility of an instance, which indicates how persistent the backbone is as clauses are removed. We propose that high-cost random instances for local search are those with very large backbones which are also backbone-fragile. We suggest that the decay in cost beyond the satisfiability threshold is due to increasing backbone robustness (the opposite of backbone fragility). Our hypothesis makes three correct predictions. First, that the backbone robustness of an instance is negatively correlated with the local search cost when other factors are controlled for. Second, that backbone-minimal instances (which are 3-SAT instances altered so as to be more backbone-fragile) are unusually hard for WSat. Third, that the clauses most often unsatisfied during search are those whose deletion has the most effect on the backbone. In understanding the pathologies of local search methods, we hope to contribute to the development of new and better techniques.

APA, Harvard, Vancouver, ISO, and other styles

31

Abu Doush, Iyad, Amal Lutfi Quran, Mohammed Azmi Al-Betar, and Mohammed A. Awadallah. "MAX-SAT Problem using Hybrid Harmony Search Algorithm." Journal of Intelligent Systems 27, no. 4 (October 25, 2018): 643–58. http://dx.doi.org/10.1515/jisys-2016-0129.

Full text

Abstract:

Abstract Maximum Satisfiability problem is an optimization variant of the Satisfiability problem (SAT) denoted as MAX-SAT. The aim of this problem is to find Boolean variable assignment that maximizes the number of satisfied clauses in the Boolean formula. In case the number of variables per clause is equal or greater than three, then this problem is considered NP-complete. Hence, many researchers have developed techniques to deal with MAX-SAT. In this paper, we investigate the impact of different hybrid versions of binary harmony search (HS) algorithm on solving MAX 3-SAT problem. Therefore, we propose two novel hybrid binary HS algorithms. The first hybridizes Flip heuristic with HS, and the second uses Tabu search combined with Flip heuristic. Furthermore, a distinguished feature of our proposed approaches is using an objective function that is updated dynamically based on the stepwise adaptation of weights (SAW) mechanism to evaluate the MAX-SAT solution using the proposed hybrid versions. The performance of the proposed approaches is evaluated over standard MAX-SAT benchmarks, and the results are compared with six evolutionary algorithms and three stochastic local search algorithms. The obtained results are competitive and show that the proposed novel approaches are effective.

APA, Harvard, Vancouver, ISO, and other styles

32

JACOBSON, S., and L. MCLAY. "Applying statistical tests to empirically compare tabu search parameters for MAX 3-SATISFIABILITY: A case study☆." Omega 37, no. 3 (June 2009): 522–34. http://dx.doi.org/10.1016/j.omega.2007.09.003.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Galatenko, Alexei V., Stepan A. Nersisyan, and Dmitriy N. Zhuk. "NP-Hardness of the Problem of Optimal Box Positioning." Mathematics 7, no. 8 (August 6, 2019): 711. http://dx.doi.org/10.3390/math7080711.

Full text

Abstract:

We consider the problem of finding a position of a d-dimensional box with given edge lengths that maximizes the number of enclosed points of the given finite set P ⊂ R d , i.e., the problem of optimal box positioning. We prove that while this problem is polynomial for fixed values of d, it is NP-hard in the general case. The proof is based on a polynomial reduction technique applied to the considered problem and the 3-CNF satisfiability problem.

APA, Harvard, Vancouver, ISO, and other styles

34

Cocco, Simona, and Rémi Monasson. "Trajectories in Phase Diagrams, Growth Processes, and Computational Complexity: How Search Algorithms Solve the 3-Satisfiability Problem." Physical Review Letters 86, no. 8 (February 19, 2001): 1654–57. http://dx.doi.org/10.1103/physrevlett.86.1654.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

TEO, JASON, and HUSSEIN A. ABBASS. "A TRUE ANNEALING APPROACH TO THE MARRIAGE IN HONEY-BEES OPTIMIZATION ALGORITHM." International Journal of Computational Intelligence and Applications 03, no. 02 (June 2003): 199–211. http://dx.doi.org/10.1142/s146902680300094x.

Full text

Abstract:

Marriage in Honey-Bees Optimization is a new swarm intelligence technique inspired by the marriage process of honey-bees. It has been shown to be very effective in solving the propositional satisfiability problem known as 3-SAT. The objective of this paper is to test a conventional annealing approach as the basis for determining the pool of drones. The modified algorithm is tested using a group of randomly generated hard 3-SAT problems to compare its behavior and efficiency against previous implementations. The overall performance of the MBO algorithm was found to have improved significantly using the proposed annealing function. Furthermore, a dramatic improvement was noted with the committee machine using this true annealing approach.

APA, Harvard, Vancouver, ISO, and other styles

36

Chieu, H. L., and W. S. Lee. "Relaxed Survey Propagation for The Weighted Maximum Satisfiability Problem." Journal of Artificial Intelligence Research 36 (October 30, 2009): 229–66. http://dx.doi.org/10.1613/jair.2808.

Full text

Abstract:

The survey propagation (SP) algorithm has been shown to work well on large instances of the random 3-SAT problem near its phase transition. It was shown that SP estimates marginals over covers that represent clusters of solutions. The SP-y algorithm generalizes SP to work on the maximum satisfiability (Max-SAT) problem, but the cover interpretation of SP does not generalize to SP-y. In this paper, we formulate the relaxed survey propagation (RSP) algorithm, which extends the SP algorithm to apply to the weighted Max-SAT problem. We show that RSP has an interpretation of estimating marginals over covers violating a set of clauses with minimal weight. This naturally generalizes the cover interpretation of SP. Empirically, we show that RSP outperforms SP-y and other state-of-the-art Max-SAT solvers on random Max-SAT instances. RSP also outperforms state-of-the-art weighted Max-SAT solvers on random weighted Max-SAT instances.

APA, Harvard, Vancouver, ISO, and other styles

37

Maksimenko, Aleksandr N. "On a family of 0/1-polytopes with an NP-complete criterion for vertex nonadjacency relation." Discrete Mathematics and Applications 29, no. 1 (February 25, 2019): 7–14. http://dx.doi.org/10.1515/dma-2019-0002.

Full text

Abstract:

Abstract In 1995 T. Matsui considered a special family of 0/1-polytopes with an NP-complete criterion for vertex nonadjacency relation. In 2012 the author demonstrated that all polytopes of this family appear as faces of polytopes associated with the following NP-complete problems: the travelling salesman problem, the 3-satisfiability problem, the knapsack problem, the set covering problem, the partial ordering problem, the cube subgraph problem, and some others. Here it is shown that none of the polytopes of the aforementioned special family (with the exception of the one-dimensional segment) can appear as a face in a polytope associated with the problem of the maximum independent set, the set packing problem, the set partitioning problem, and the problem of 3-assignments.

APA, Harvard, Vancouver, ISO, and other styles

38

Kashintsev, E. V. "On satisfiability of the C'(1/3) and C(4) conditions for special homogeneous semigroups with defining word-powers." Mathematical Notes 54, no. 3 (September 1993): 903–7. http://dx.doi.org/10.1007/bf01209555.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Heule, Marijn. "Introduction to Mathematics of Satisfiability, Victor W. Marek, Chapman & Hall/CRC, 2009. Hardback, ISBN-13: 978-143980167-3, $89.95." Theory and Practice of Logic Programming 11, no. 1 (August 18, 2010): 126–30. http://dx.doi.org/10.1017/s1471068410000451.

Full text

APA, Harvard, Vancouver, ISO, and other styles

40

Fu, Huimin, Yang Xu, Shuwei Chen, and Jun Liu. "Improving WalkSAT for Random 3-SAT Problems." JUCS - Journal of Universal Computer Science 26, no. 2 (February 28, 2020): 220–43. http://dx.doi.org/10.3897/jucs.2020.013.

Full text

Abstract:

Stochastic local search (SLS) algorithms are well known for their ability to efficiently find models of random instances of the Boolean satisfiability (SAT) problems. One of the most famous SLS algorithms for SAT is called WalkSAT, which has wide influence and performs well on most of random 3-SAT instances. However, the performance of WalkSAT lags far behind on random 3-SAT instances equal to or greater than the phase transition ratio. Motivated by this limitation, in the present work, firstly an allocation strategy is introduced and utilized in WalkSAT to determine the initial assignment, leading to a new algorithm called WalkSATvav. The experimental results show that WalkSATvav significantly outperforms the state-of-the-art SLS solvers on random 3-SAT instances at the phase transition for SAT Competition 2017. However, WalkSATvav cannot rival its competitors on random 3-SAT instances greater than the phase transition ratio. Accordingly, WalkSATvav is further improved for such instances by utilizing a combination of an improved genetic algorithm and an improved ant colony algorithm, which complement each other in guiding the search direction. The resulting algorithm, called WalkSATga, is far better than WalkSAT and significantly outperforms some previous known SLS solvers on random 3-SAT instances greater than the phase transition ratio from SAT Competition 2017. Finally, a new SAT solver called WalkSATlg, which combines WalkSATvav and WalkSATga, is proposed, which is competitive with the winner of random satisfiable category of SAT competition 2017 on random 3-SAT problem.

APA, Harvard, Vancouver, ISO, and other styles

41

Zamri, Nur Ezlin, Mohd Asyraf Mansor, Mohd Shareduwan Mohd Kasihmuddin, Alyaa Alway, Siti Zulaikha Mohd Jamaludin, and Shehab Abdulhabib Alzaeemi. "Amazon Employees Resources Access Data Extraction via Clonal Selection Algorithm and Logic Mining Approach." Entropy 22, no. 6 (May 27, 2020): 596. http://dx.doi.org/10.3390/e22060596.

Full text

Abstract:

Amazon.com Inc. seeks alternative ways to improve manual transactions system of granting employees resources access in the field of data science. The work constructs a modified Artificial Neural Network (ANN) by incorporating a Discrete Hopfield Neural Network (DHNN) and Clonal Selection Algorithm (CSA) with 3-Satisfiability (3-SAT) logic to initiate an Artificial Intelligence (AI) model that executes optimization tasks for industrial data. The selection of 3-SAT logic is vital in data mining to represent entries of Amazon Employees Resources Access (AERA) via information theory. The proposed model employs CSA to improve the learning phase of DHNN by capitalizing features of CSA such as hypermutation and cloning process. This resulting the formation of the proposed model, as an alternative machine learning model to identify factors that should be prioritized in the approval of employees resources applications. Subsequently, reverse analysis method (SATRA) is integrated into our proposed model to extract the relationship of AERA entries based on logical representation. The study will be presented by implementing simulated, benchmark and AERA data sets with multiple performance evaluation metrics. Based on the findings, the proposed model outperformed the other existing methods in AERA data extraction.

APA, Harvard, Vancouver, ISO, and other styles

42

Ciampiconi, Lorenzo, Bishwamittra Ghosh, Jonathan Scarlett, and Kuldeep S. Meel. "A MaxSAT-Based Framework for Group Testing." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 06 (April 3, 2020): 10144–52. http://dx.doi.org/10.1609/aaai.v34i06.6574.

Full text

Abstract:

The success of MaxSAT (maximum satisfiability) solving in recent years has motivated researchers to apply MaxSAT solvers in diverse discrete combinatorial optimization problems. Group testing has been studied as a combinatorial optimization problem, where the goal is to find defective items among a set of items by performing sets of tests on items. In this paper, we propose a MaxSAT-based framework, called MGT, that solves group testing, in particular, the decoding phase of non-adaptive group testing. We extend this approach to the noisy variant of group testing, and propose a compact MaxSAT-based encoding that guarantees an optimal solution. Our extensive experimental results show that MGT can solve group testing instances of 10000 items with 3% defectivity, which no prior work can handle to the best of our knowledge. Furthermore, MGT has better accuracy than the LP-based approach. We also discover an interesting phase transition behavior in the runtime, which reveals the easy-hard-easy nature of group testing.

APA, Harvard, Vancouver, ISO, and other styles

43

Kundu, Sudeshna, Suchismita Roy, and Shyamapada Mukherjee. "Rectilinear Steiner Tree Construction Techniques Using PB-SAT-Based Methodology." Journal of Circuits, Systems and Computers 29, no. 04 (July 5, 2019): 2050057. http://dx.doi.org/10.1142/s0218126620500577.

Full text

Abstract:

Rectilinear Steiner Tree (RST) construction is a fundamental problem in very large scale integration (VLSI) physical design. Its applications include placement and routing in VLSI physical design automation (PDA) where wire length and timing estimations for signal nets are obtained. In this paper, a pseudo-Boolean satisfiability (PB-SAT)-based approach is presented to solve rectilinear Steiner tree problem. But large nets are a bottleneck for any SAT-based approach. Hence, to deal with large nets, a region-partitioning-based algorithm is taken into consideration, which eventually achieves a reasonable running time. Furthermore, a clustering-based approach is also explored to improve the partitioning of nets by identifying clusters and then applying a heuristic-based approach to get the minimum wire length for each set of the clusters. Experimental results obtained by these techniques show that the proposed algorithm can solve the RST problem very effectively even on large circuits and it outperforms the widely used RST algorithm FLUTE with 3[Formula: see text][Formula: see text][Formula: see text]to 9[Formula: see text][Formula: see text][Formula: see text]speedups.

APA, Harvard, Vancouver, ISO, and other styles

44

Cai, S., C. Luo, and K. Su. "Scoring Functions Based on Second Level Score for k-SAT with Long Clauses." Journal of Artificial Intelligence Research 51 (October 22, 2014): 413–41. http://dx.doi.org/10.1613/jair.4480.

Full text

Abstract:

It is widely acknowledged that stochastic local search (SLS) algorithms can efficiently find models for satisfiable instances of the satisfiability (SAT) problem, especially for random k-SAT instances. However, compared to random 3-SAT instances where SLS algorithms have shown great success, random k-SAT instances with long clauses remain very difficult. Recently, the notion of second level score, denoted as "score_2", was proposed for improving SLS algorithms on long-clause SAT instances, and was first used in the powerful CCASat solver as a tie breaker. In this paper, we propose three new scoring functions based on score_2. Despite their simplicity, these functions are very effective for solving random k-SAT with long clauses. The first function combines score and score_2, and the second one additionally integrates the diversification property "age". These two functions are used in developing a new SLS algorithm called CScoreSAT. Experimental results on large random 5-SAT and 7-SAT instances near phase transition show that CScoreSAT significantly outperforms previous SLS solvers. However, CScoreSAT cannot rival its competitors on random k-SAT instances at phase transition. We improve CScoreSAT for such instances by another scoring function which combines score_2 with age. The resulting algorithm HScoreSAT exhibits state-of-the-art performance on random k-SAT (k>3) instances at phase transition. We also study the computation of score_2, including its implementation and computational complexity.

APA, Harvard, Vancouver, ISO, and other styles

45

Li, C. M., F. Manya, and J. Planes. "New Inference Rules for Max-SAT." Journal of Artificial Intelligence Research 30 (October 23, 2007): 321–59. http://dx.doi.org/10.1613/jair.2215.

Full text

Abstract:

Exact Max-SAT solvers, compared with SAT solvers, apply little inference at each node of the proof tree. Commonly used SAT inference rules like unit propagation produce a simplified formula that preserves satisfiability but, unfortunately, solving the Max-SAT problem for the simplified formula is not equivalent to solving it for the original formula. In this paper, we define a number of original inference rules that, besides being applied efficiently, transform Max-SAT instances into equivalent Max-SAT instances which are easier to solve. The soundness of the rules, that can be seen as refinements of unit resolution adapted to Max-SAT, are proved in a novel and simple way via an integer programming transformation. With the aim of finding out how powerful the inference rules are in practice, we have developed a new Max-SAT solver, called MaxSatz, which incorporates those rules, and performed an experimental investigation. The results provide empirical evidence that MaxSatz is very competitive, at least, on random Max-2SAT, random Max-3SAT, Max-Cut, and Graph 3-coloring instances, as well as on the benchmarks from the Max-SAT Evaluation 2006.

APA, Harvard, Vancouver, ISO, and other styles

46

Wu, Hao, and Marie Farrell. "A formal approach to finding inconsistencies in a metamodel." Software and Systems Modeling 20, no. 4 (January 29, 2021): 1271–98. http://dx.doi.org/10.1007/s10270-020-00849-8.

Full text

Abstract:

AbstractChecking the consistency of a metamodel involves finding a valid metamodel instance that provably meets the set of constraints that are defined over the metamodel. These constraints are often specified in Object Constraint Language. Often, a metamodel is inconsistent due to conflicts among the constraints. Existing approaches and tools are typically incapable of pinpointing the conflicting constraints, and this makes it difficult for users to debug and fix their metamodels. In this paper, we present a formal approach for locating conflicting constraints in inconsistent metamodels. Our approach has four distinct features: (1) users can rank individual metamodel features using their own domain-specific knowledge, (2) we transform these ranked features to a weighted maximum satisfiability modulo theories problem and solve it to compute the set of maximum achievable features, (3) we pinpoint the conflicting constraints by solving the set cover problem using a novel algorithm, and (4) we have implemented our approach into a fully automated tool called MaxUSE. Our evaluation results, using our assembled set of benchmarks, demonstrate the scalability of our work and that it is capable of efficiently finding conflicting constraints.

APA, Harvard, Vancouver, ISO, and other styles

47

Shah, Kunal, Grant Ballard, Annie Schmidt, and Mac Schwager. "Multidrone aerial surveys of penguin colonies in Antarctica." Science Robotics 5, no. 47 (October 28, 2020): eabc3000. http://dx.doi.org/10.1126/scirobotics.abc3000.

Full text

Abstract:

Speed is essential in wildlife surveys due to the dynamic movement of animals throughout their environment and potentially extreme changes in weather. In this work, we present a multirobot path-planning method for conducting aerial surveys over large areas designed to make the best use of limited flight time. Unlike current survey path-planning solutions based on geometric patterns or integer programs, we solve a series of satisfiability modulo theory instances of increasing complexity. Each instance yields a set of feasible paths at each iteration and recovers the set of shortest paths after sufficient time. We implemented our planning algorithm with a team of drones to conduct multiple photographic aerial wildlife surveys of Cape Crozier, one of the largest Adélie penguin colonies in the world containing more than 300,000 nesting pairs. Over 2 square kilometers was surveyed in about 3 hours. In contrast, previous human-piloted single-drone surveys of the same colony required over 2 days to complete. Our method reduces survey time by limiting redundant travel while also allowing for safe recall of the drones at any time during the survey. Our approach can be applied to other domains, such as wildfire surveys in high-risk weather conditions or disaster response.

APA, Harvard, Vancouver, ISO, and other styles

48

Rozier, Kristin Y., and Moshe Y. Vardi. "LTL satisfiability checking." International Journal on Software Tools for Technology Transfer 12, no. 2 (March 11, 2010): 123–37. http://dx.doi.org/10.1007/s10009-010-0140-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Selman, Bart, David G. Mitchell, and Hector J. Levesque. "Generating hard satisfiability problems." Artificial Intelligence 81, no. 1-2 (March 1996): 17–29. http://dx.doi.org/10.1016/0004-3702(95)00045-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

Barto, Libor, Jakub Bulín, Andrei Krokhin, and Jakub Opršal. "Algebraic Approach to Promise Constraint Satisfaction." Journal of the ACM 68, no. 4 (July 7, 2021): 1–66. http://dx.doi.org/10.1145/3457606.

Full text

Abstract:

The complexity and approximability of the constraint satisfaction problem (CSP) has been actively studied over the past 20 years. A new version of the CSP, the promise CSP (PCSP), has recently been proposed, motivated by open questions about the approximability of variants of satisfiability and graph colouring. The PCSP significantly extends the standard decision CSP. The complexity of CSPs with a fixed constraint language on a finite domain has recently been fully classified, greatly guided by the algebraic approach, which uses polymorphisms—high-dimensional symmetries of solution spaces—to analyse the complexity of problems. The corresponding classification for PCSPs is wide open and includes some long-standing open questions, such as the complexity of approximate graph colouring, as special cases. The basic algebraic approach to PCSP was initiated by Brakensiek and Guruswami, and in this article, we significantly extend it and lift it from concrete properties of polymorphisms to their abstract properties. We introduce a new class of problems that can be viewed as algebraic versions of the (Gap) Label Cover problem and show that every PCSP with a fixed constraint language is equivalent to a problem of this form. This allows us to identify a “measure of symmetry” that is well suited for comparing and relating the complexity of different PCSPs via the algebraic approach. We demonstrate how our theory can be applied by giving both general and specific hardness/tractability results. Among other things, we improve the state-of-the-art in approximate graph colouring by showing that, for any k ≥ 3, it is NP-hard to find a (2 k -1)-colouring of a given k -colourable graph.

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!