Search

Within the swiftly evolving domain of neural networks, the discrete Hopfield-SAT model, endowed with logical rules and the ability to achieve global minima of SAT problems, has emerged as a novel prototype for SAT solvers, capturing significant scientific interest. However, this model shows substantial sensitivity to network size and logical complexity. As the number of neurons and logical complexity increase, the solution space rapidly contracts, leading to a marked decline in the model's problem-solving performance. This paper introduces a novel discrete Hopfield-SAT model, enhanced by Crow search-guided fuzzy clustering hybrid optimization, effectively addressing this challenge and significantly boosting solving speed. The proposed model unveils a significant insight: its uniquely designed cost function for initial assignments introduces a quantification mechanism that measures the degree of inconsistency within its logical rules. Utilizing this for clustering, the model utilizes a Crow search-guided fuzzy clustering hybrid optimization to filter potential solutions from initial assignments, substantially narrowing the search space and enhancing retrieval efficiency. Experiments were conducted with both simulated and real datasets for 2SAT problems. The results indicate that the proposed model significantly surpasses traditional discrete Hopfield-SAT models and those enhanced by genetic-guided fuzzy clustering optimization across key performance metrics: Global minima ratio, Hamming distance, CPU time, retrieval rate of stable state, and retrieval rate of global minima, particularly showing statistically significant improvements in solving speed. These advantages play a pivotal role in advancing the discrete Hopfield-SAT model towards becoming an exemplary SAT solver. Additionally, the model features exceptional parallel computing capabilities and possesses the potential to integrate with other logical rules. In the future, this optimized model holds promise as an effective tool for solving more complex SAT problems.

We thoroughly study a novel but basic combinatorial matrix completion problem: Given a binary incomplete matrix, fill in the missing entries so that every pair of rows in the resulting matrix has a Hamming distance within a specified range. We obtain an almost complete picture of the complexity landscape regarding the distance constraints and the maximum number of missing entries in any row. We develop polynomial-time algorithms for maximum diameter three based on Deza's theorem (1973) [11] from extremal set theory. We also prove NP-hardness for diameter at least four. For the number of missing entries per row, we show polynomial-time solvability when there is only one and NP-hardness when there can be at least two. In many of our algorithms, we heavily rely on Deza's theorem to identify sunflower structures. This paves the way towards polynomial-time algorithms which are based on finding graph factors and solving 2-SAT instances. [ABSTRACT FROM AUTHOR]

We show that throughout the satisfiable phase the normalized number of satisfying assignments of a random 2‐SAT formula converges in probability to an expression predicted by the cavity method from statistical physics. The proof is based on showing that the Belief Propagation algorithm renders the correct marginal probability that a variable is set to "true" under a uniformly random satisfying assignment. [ABSTRACT FROM AUTHOR]

In this paper we study a problem of determining when entities are active based on their interactions with each other. We consider a set of entities V and a sequence of time-stamped edges E among the entities. Each edge (u , v , t) ∈ E denotes an interaction between entities u and v at time t. We assume an activity model where each entity is active during at most k time intervals. An interaction (u, v, t) can be explained if at least one of u or v are active at time t. Our goal is to reconstruct the activity intervals for all entities in the network, so as to explain the observed interactions. This problem, the network-untangling problem, can be applied to discover event timelines from complex entity interactions. We provide two formulations of the network-untangling problem: (i) minimizing the total interval length over all entities (sum version), and (ii) minimizing the maximum interval length (max version). We study separately the two problems for k = 1 and k > 1 activity intervals per entity. For the case k = 1 , we show that the sum problem is NP-hard, while the max problem can be solved optimally in linear time. For the sum problem we provide efficient algorithms motivated by realistic assumptions. For the case of k > 1 , we show that both formulations are inapproximable. However, we propose efficient algorithms based on alternative optimization. We complement our study with an evaluation on synthetic and real-world datasets, which demonstrates the validity of our concepts and the good performance of our algorithms. [ABSTRACT FROM AUTHOR]

In this study, a hybrid approach that employs Hopfield neural network and a genetic algorithm in doing k-SAT problems was proposed. The Hopfield neural network was used to minimise logical inconsistency in interpreting logic clauses or programme. Hybrid optimisation made use of the global convergence advantage of the genetic algorithm to deal with learning complexity in the Hopfield network. The simulation incorporated with genetic algorithm and exhaustive search method with different k-Satisfiability (k-SAT) problems, namely, the Horn-Satisfiability (HORN-SAT), 2-Satisfiability (2-SAT) and 3-Satisfiability (3-SAT) will be developed by using Microsoft Visual C++ 2010 Express Software. The performance of both searching techniques was evaluated based on global minima ratio, hamming distance and computation time. Simulated results suggested that the genetic algorithm outperformed exhaustive search in doing k-SAT logic programming in the Hopfield network. [ABSTRACT FROM AUTHOR]

A binary phylogenetic network may or may not be obtainable from a tree by the addition of directed edges (arcs) between tree arcs. Here, we establish a precise and easily tested criterion (based on "2-SAT") that efficiently determines whether or not any given network can be realized in this way. Moreover, the proof provides a polynomial-time algorithm for finding one or more trees (when they exist) on which the network can be based. A number of interesting consequences are presented as corollaries; these lead to some further relevant questions and observations, which we outline in the conclusion. [ABSTRACT FROM AUTHOR]

Abstract: A star in an undirected graph is a tree in which at most one vertex has degree larger than one. A star forest is a collection of vertex disjoint stars. An out-star (in-star) in a digraph is a star in the underlying undirected graph of such that all edges are directed out of (into) the center. The problem of partitioning the edges of the underlying graph of a digraph into two star forests and is known to be NP-complete. On the other hand, with the additional requirement for and to be forests of out-stars the problem becomes polynomial (via an easy reduction to 2-SAT). In this article we settle the complexity of problems lying in between these two problems. Namely, we study the complexity of the related problems where we require each to be a forest of stars in the underlying sense and require (in different problems) that in , is either a forest of out-stars, in-stars, out- or in-stars or just stars in the underlying sense. [Copyright &y& Elsevier]

We describe a limiting distribution for the number of connected components in the subgraph of the discrete cube induced by the satisfying assignments to a random 2-SAT formula. We show that, for the probability range where formulas are likely to be satisfied, the random number of components converges weakly (in the number of variables) to a distribution determined by a Poisson random variable. The number of satisfying assignments or solutions is known to grow exponentially in the number of variables. Thus, our result implies that exponentially many solutions are organized into a stochastically bounded number of components. We also describe an application to biological evolution; in particular, to a type of fitness landscape where satisfying assignments represent viable genotypes and connectivity of genotypes is limited by single site mutations. The biological result is that, with probability approaching 1, each viable genotype is connected by single site mutations to an exponential number of other viable genotypes while the number of viable clusters is finite. [ABSTRACT FROM AUTHOR]

Abstract: An undirected graph is a probe graph if its vertex set can be partitioned into two sets, (nonprobes) and (probes) where is independent and there exists such that is a graph. In this article we investigate probe threshold and probe trivially perfect graphs and characterise them in terms of certain 2-Sat formulas and in other ways. For the case when the partition into probes and nonprobes is given, we give characterisations by forbidden induced subgraphs, linear recognition algorithms (in the case of probe threshold graphs it is based on the degree sequence of the graph), and linear algorithms to find a set of minimum size. Furthermore, we give linear time recognition algorithms for both classes and a characterisation by forbidden subgraphs for probe threshold graphs when the partition is not given. [Copyright &y& Elsevier]

Abstract: Nonograms, also known as Japanese puzzles, are a specific type of logic drawing puzzles. The challenge is to fill a grid with black and white pixels in such a way that a given description for each row and column, indicating the lengths of consecutive segments of black pixels, is adhered to. Although the Nonograms in puzzle books can usually be solved by hand, the general problem of solving Nonograms is NP-hard. In this paper, we propose a reasoning framework that can be used to determine the value of certain pixels in the puzzle, given a partial filling. Constraints obtained from relaxations of the Nonogram problem are combined into a 2-Satisfiability (2-SAT) problem, which is used to deduce pixel values in the Nonogram solution. By iterating this procedure, starting from an empty grid, it is often possible to solve the puzzle completely. All the computations involved in the solution process can be performed in polynomial time. Our experimental results demonstrate that the approach is capable of solving a variety of Nonograms that cannot be solved by simple logic reasoning within individual rows and columns, without resorting to branching operations. In addition, we present statistical results on the solvability of Nonograms, obtained by applying our method to a large number of Nonograms. [Copyright &y& Elsevier]

Abstract: In a partial Latin square P a set of distinct entries, such that no two of which are in the same row or column is called a transversal. By the size of a transversal , we mean the number of its entries. We define a duplex to be a partial Latin square of order containing entries such that exactly two entries lie in each row and column and each of symbols occurs exactly twice. We show that determining the maximum size of a transversal in a given duplex is an -complete problem. This problem relates to independent sets in certain subfamilies of cubic graphs. Generalizing the concept of transversals in edge coloring of graphs we are led to introduce the concept of rainbow matching. We show that if each color appears at most twice then it is a polynomial time problem to know whether there exists a rainbow matching of size at least for each fixed , where is the order of the graph. As an application we show that for any fixed , there is a polynomial time algorithm which decides whether , for any graph on vertices containing a perfect matching. At the end we mention some other applications of rainbow matching. [Copyright &y& Elsevier]

Abstract: A skew partition as defined by Chvátal is a partition of the vertex set of a graph into four nonempty parts such that there are all possible edges between and , and no edges between and . We introduce the concept of -extended skew partition which includes all partitioning problems into nonempty parts such that there are all possible edges between the parts, no edges between the parts, , which generalizes the skew partition. We present a polynomial-time algorithm for testing whether a graph admits an -extended skew partition. As a tool to complete this task we also develop a generalized 2-SAT algorithm, which by itself may have application to other partition problems. [Copyright &y& Elsevier]

Abstract: An instance of a constraint satisfaction problem is l-consistent if any l constraints of it can be simultaneously satisfied. For a set of constraint types, denotes the largest ratio of constraints which can be satisfied in any l-consistent instance composed by constraints of types from . In the case of sets consisting of finitely many Boolean predicates, we express the limit as the minimum of a certain functional on a convex set of polynomials. Our results yield a robust deterministic algorithm (for a fixed set ) running in time linear in the size of the input and which finds either an inconsistent set of constraints (of size bounded by the function of ) or a truth assignment which satisfies the fraction of at least of the given constraints. We also compute the values of for several specific predicates P. [Copyright &y& Elsevier]

The sign pattern of a real matrix A is the matrix obtained by replacing each entry of A by its sign. A real matrix A is an L-matrix if every real matrix with the same sign pattern as A has linearly independent columns. L-matrices arise naturally in and are essential to the study of sign-solvability and related notions. In special cases, the L-matrix property has connections to the even dicycle problem, Pfaffian orientations, and Po´lya’s permanent problem. Unfortunately, the problem of recognizing L-matrices is known to be co-NP-complete in general. We elaborate in this vein by showing a polynomial-time inapproximability result for Max-not-L-rows, a particular optimization version of L-matrix recognition, by means of an approximation-preserving reduction from the previously studied problem Max-not-equal-2-Sat. [Copyright &y& Elsevier]