You are an expert at summarizing long articles. Proceed to summarize the following text: 
understanding the nature of complexity in np - hard optimization problems is an important goal in the study of complex systems @xcite . most of optimization problems are indeed a constraint satisfaction problem and satisfiability problem is a prototype of such problems @xcite . in a satisfiability problem one looks for a configuration of logical variables that satisfies a number of logical constraints ( clauses ) . a clause is in turn disjunction of a few logical variables . in random k - satisfiability ( k - sat ) problem a clause involves @xmath0 randomly selected variables each negated with a given probability . increasing the number of clauses per variables , these problems display a phase transition from satisfiable to unsatisfiable phase @xcite . it is around this sat - unsat transition that the typical complexity of the problem raises rapidly . in fact the transition is preceded by a clustering of solutions in the configuration space , a phenomenon known as replica symmetry breaking in physics literatures @xcite . there are a few analytic methods and algorithms , such as replica and cavity methods and survey propagation algorithm @xcite , that deal with the behavior of random satisfiability problems . + here we are going to look at the problem from a rather geometrical point of view . we know that there are efficient algorithms such as walksat and belief propagation @xcite that can efficiently solve a random k - sat problem possessing a tree factor graph ; a factor graph is a bipartite - graph representation of constraint satisfaction problems . we also know that spanning trees are the closest tree structures to a given graph . then it is interesting to find the relation between the solutions of a factor graph and the solutions of its spanning trees . this relation could result in the reduction of the original problem to easier ones . + in this paper we show that there is indeed a correspondence between the solutions of a random k - sat problem and those of spanning trees in the associated factor graph . in principle to check that a random k - sat problem is satisfied or not one has to check the satisfiability of all the spanning trees . the main problem is that in general the number of spanning trees grows exponentially with the size of graph . moreover we will see that even when we are in the sat phase almost all randomly generated spanning trees are unsatisfiable . to get around this problem we assign a weight to each edge of the factor graph . for an edge , its weight is taken as the probability that the edge to be present in the graph . then we suggest an ansatz that relates the above probability to the survey of warnings sent along the edge and run survey propagation algorithm . this algorithm converges with a nonzero probability in the sat phase and we find that in this case all maximum spanning trees ( which have the maximum sum of weights on their edges ) are satisfied . in other words , the above algorithm defines null edges of the factor graph . + the structure of paper is as follows ; in section [ 2 ] we define the problem more precisely and illustrate the relation between a factor graph and its spanning trees . we briefly deal with the satisfiability of randomly generated spanning trees in section [ 3 ] . in section [ 4 ] we modify the survey propagation algorithm to generate satisfiable spanning trees . section [ 5 ] includes our concluding remarks . a random satisfiability problem is defined as follows : we take @xmath1 logical variables @xmath2 . then we construct a formula @xmath3 of @xmath4 clauses joined to each other by logical and . each clause contains a number of randomly selected logical variables . in random k - sat problem each clause has a fixed number of @xmath0 variables . these variables , which join to each other by logical or , are negated with probability @xmath5 and appear as such with probability @xmath6 . for example @xmath7 is a 2-sat formula with @xmath8 clauses and @xmath9 logical variables . a solution of @xmath3 is a configuration of logical variables that satisfy all clauses . + the relevant parameter that determines the satisfiability of @xmath3 is @xmath10 . in the thermodynamic limit ( @xmath11 and @xmath12 ) @xmath3 is satisfied with probability one as long as @xmath13 . moreover , it has been found that for @xmath14 the problem is in the hard - sat phase @xcite . at @xmath15 we have a dynamical phase transition associated with the break down of replica symmetry . assuming one - step replica symmetry breaking , one obtains @xmath16 and @xmath17 for random 3-sat problems with @xmath18 @xcite . although this approximation seems to be exact near the sat - unsat transition but it fails close to the dynamical transition where higher order replica symmetry breaking solutions are to be used @xcite . the above approximation allows us to compute the configurational entropy or complexity of the problem . the complexity , which is logarithm of the number of clusters in the solution space , takes abruptly a nonzero value at @xmath15 and decreases to zero at @xmath19 . + the factor graph is a bipartite graph of variable nodes and function nodes ( clauses ) . the structure of this graph is completely determined by an @xmath20 matrix with elements @xmath21 ; @xmath22 if clause @xmath23 contains @xmath24 , it is equal to @xmath25 if @xmath26 appears in @xmath23 and otherwise @xmath27 . + now consider a random k - sat problem and the associated factor graph . in the sat phase the problem has some solutions that satisfy all the clauses . the factor graph has a number of spanning trees which have their own solutions . these solutions can be easily obtained by walksat algorithm or some other local search algorithms @xcite . notice that a spanning tree could have no solution even when the original problem is satisfied . here we show that ( i ) _ each solution of a spanning tree is the solution of the original graph too . _ and ( ii ) _ each solution of the original graph is the solution of at least one of the spanning trees_. + note that in a spanning tree each function node is connected to a smaller number of variable nodes than in the original graph . thus if a configuration of variable nodes satisfies a spanning tree it should also satisfy the original problem . + to verify the second statement we start with a solution of the problem and try to construct a spanning tree that is also satisfied by this solution . to this end we have to remove some of the edges in the graph until no cycle remains in the factor graph . during this process we should , of course , respect the graph connectedness and more importantly satisfaction of all the function nodes . therefore , at each step we consider a cycle of the graph and remove one of the null edges along this cycle . a null edge is an edge that its removal dos not change the number of satisfied clauses . this removal also preserves the graph connectedness . note that a null edge at a given stage may not be a null one in the next stages . + to complete the proof we should show that for a solution of the factor graph , any cycle in the graph has at least one null edge . first notice that each function node which lies on a cycle has at least two neighbors . since we are dealing with a solution then at least one of its neighboring variable nodes satisfies the function node . in this case at least one of the edges along the cycle will be a null edge and we can freely remove it from the graph . + indeed for any solution , a cycle would have a large number of null edges which result in a large degree of freedom in constructing the desired spanning tree . the number of null edges along a cycle would be of order of the number of function nodes in the cycle . it means that an arbitrary solution appears in a large number of spanning trees . + suppose that we have a satisfiable spanning tree . then we can use a local search algorithm to find its solutions . notice that for a tree factor graph there is no frustration in the problem and one can safely assume all the solutions in the same cluster . indeed , warning propagation algorithm @xcite which is based on this assumption gives exact results for tree factor graphs . thus we expect that the solutions of a satisfiable spanning tree lay in the same cluster of solutions . in the thermodynamic limit , it means that for any two solutions , there is at least one path in the solution space that connects them to each other . the path starts from one of the solutions and reach the other one by successive steps of finite lengths . since the solutions also satisfy the original problem we may conclude that they lay in the same cluster of the original problem too . + please notice that one could use the same arguments ( as given in this section ) to show that any configuration of variables that violates @xmath28 clauses in the original factor graph also appears in at least one of the spanning trees . therefore , the state with minimum @xmath28 ( the ground state ) in the original factor graph , has also the minimum @xmath28 among the ground states of all the spanning trees . there is an algorithm that uses a simple random walker on the original factor graph and generates ( with a uniform measure ) a spanning tree @xcite . using this algorithm we generated up to @xmath29 spanning trees of the factor graph of a random 3-sat problem with @xmath30 . belief propagation algorithm can be used to compute the entropy ( logarithm of the number of solutions ) of each spanning tree . we found that when @xmath31 both the average entropy and its dispersion decrease exponentially with @xmath32 . however , if we increase @xmath5 slightly , we find that almost all the randomly generated spanning trees have no solution . for instance , with @xmath33 and @xmath34 , there is almost no satisfiable spanning tree among @xmath29 randomly generated ones . in this case , in average about @xmath35 clauses are not satisfied . when we increase @xmath5 to @xmath36 the average number of unsatisfied clauses in a randomly generated spanning tree increases to @xmath37 whereas the original problem is satisfiable . we found that any naive attempt , like the generalization of simple random walk procedure to a biased one , fails in generating satisfiable spanning trees . these observations show that finding satisfiable spanning trees is not an easy task . in the following we look for a more sophisticated way to solve this problem . we will restrict ourselves to random 3-sat problems in the most random case , i.e. @xmath18 . in section [ 2 ] we used the notion of null edges to construct spanning trees that are satisfied by a given solution . it suggests that some of the edges can be removed from the factor graph with no effect on the number of satisfied clauses . but how can we distinguish these null edges ? suppose that we remove some edges and run the survey propagation algorithm @xcite . if the problem is in the sat phase the algorithm converges with a nonzero probability and for each edge returns a survey of warnings @xmath38 . the survey @xmath38 is the probability that in an arbitrary cluster of solutions , clause @xmath23 sends a warning to variable @xmath39 . this warning enforces @xmath39 to take a value which satisfies @xmath23 . if the problem is in the unsat phase then the algorithm may still converge but it results to a negative value for the complexity . in the following we will work with a version of survey propagation algorithm in which we assign zero probability to contradictory massages . then the algorithm can end with a set of contradictory surveys . in this case a variable receives surveys that suggest different values for it and taking any value results in at least one unsatisfied clause . + let us define @xmath40 as the probability that edge @xmath41 to be present in the factor graph . then we run the survey propagation algorithm taking these probabilities into account . it means that when function node @xmath23 sends a message to its variable node @xmath39 , it gives more weights to the neighbors having a higher probability of being present in the graph . more precisely , @xmath42 is given by @xmath43,\ ] ] where @xmath44 is the probability that variable @xmath45 can not satisfy clause @xmath23 . we also denote by @xmath46 the set of variables belong to clause @xmath23 and by @xmath47 the set of clauses that variable @xmath39 contributes in . in survey propagation algorithm @xmath44 is given by @xcite @xmath48 where @xmath49 \prod_{b\in v_a^s(j)}\left(1-w_{b , j}\eta_{b\rightarrow j}\right),\\ \nonumber \pi_{j\rightarrow a}^s=[1-\prod_{b\in v_a^s(j)}\left(1-w_{b , j}\eta_{b\rightarrow j}\right)]\prod_{b\in v_a^u(j)}\left(1-w_{b , j}\eta_{b\rightarrow j}\right).\end{aligned}\ ] ] here @xmath50 denotes to the set of clauses in @xmath51 that variable @xmath45 appears in them as it appears in clause @xmath23 , see fig . [ f1 ] .     is determined by the set of surveys @xmath52 and weights @xmath53 . in this factor graph squares and circles represent clauses and variables respectively . a dashed line shows that the negated variable appears in the clause.,width=302 ]    the remaining set of clauses are denoted by @xmath54 . we should also give a way to determine @xmath40 . note that we expect a positive correlation between @xmath40 and @xmath38 . if the survey is large , the edge is necessary for satisfaction of clause @xmath23 and in the opposite case its presence is not essential . our suggested ansatz for the weights is @xmath55^{\mu},\ ] ] where @xmath56 controls the number of removed edges . for each instance of the problem we start by a random initialization for @xmath57 s and @xmath58 s . in each iteration we select all of the edges in a random way . when an edge is selected we first update @xmath38 and then @xmath40 according to eqs . ( [ eta0]-[weta ] ) . we expect that for appropriate values of @xmath59 the above algorithm converges ( without contradictory surveys ) as long as we are in the sat phase . in practice we define a maximum @xmath60 for the number of iterations @xmath61 . thus for a given @xmath59 it is possible not to reach a convergence in @xmath62 . we define @xmath63 as the probability that a randomly generated instance of the problem converges in a number of iterations less than @xmath60 . in our numerical simulations we will take @xmath64 and the limit of convergence is taken @xmath65 . note that when @xmath66 we recover the usual survey propagation algorithm on the original factor graph . in this situation the algorithm always converges and @xmath67 . increasing @xmath59 means that we are removing some of the edges and so we expect more time to reach a convergence . thus @xmath68 would be a decreasing function of its argument . we find that its behavior depends on @xmath32 , fig . in fact , @xmath63 diminishes more rapidly for greater values of @xmath32 . +    ) and satisfiability probability of a maximum spanning tree ( @xmath69 ) versus @xmath59 for a random 3-sat problem with @xmath70 and @xmath18 . the data for @xmath63 obtained from @xmath71 realizations of the problem . to obtain @xmath69 we randomly generated @xmath72 maximum spanning trees in @xmath73 satisfiable realizations . , width=302 ]    suppose that our algorithm converges . then we expect that a spanning tree with maximum sum of weights for its edges , i.e. a maximum spanning tree , be a satisfiable one . when the algorithm converges and returns the @xmath58s we can construct a maximum spanning tree as follows : starting from a randomly selected node in the original factor graph we first find the maximum weight among the edges that connect it to the other nodes . then we list the edges having a weight in the @xmath74-neighborhood of the maximum one and add randomly one of them to the new factor graph . if we repeat the addition of edges @xmath75 times we obtain a spanning tree factor graph which is a maximum spanning tree . notice that taking a nonzero interval to define the edges of maximum weight at each step , along with the randomness in choosing one of them , allow to construct a large number of maximum spanning trees . let us define @xmath76 as the probability that a maximum spanning tree be satisfiable if the algorithm converges . the best value of @xmath59 is one that for which @xmath69 takes its maximum value . in fig . [ f2 ] we also show @xmath76 for two values of @xmath77 . as the figure shows @xmath78 when @xmath79 ( @xmath80 ) and @xmath81 ( @xmath82 ) . however , as stated above , by increasing @xmath59 the convergence time increases . thus the optimal @xmath59 for @xmath77 will be around @xmath83 and @xmath84 respectively . the optimal @xmath59 decreases with @xmath32 . it means that as we get closer to the sat - unsat transition we have to give more importance to the surveys . +    ) and satisfiability probability of a maximum spanning tree ( @xmath69 ) versus @xmath59 for random 3-sat problems of different sizes with @xmath18 . here the statistical errors are of order @xmath85.,width=302 ]    to see the finite size effects we run the algorithm for larger problem sizes @xmath86 . the results for @xmath63 and @xmath69 at @xmath82 have been shown in fig . the convergence probability decreases more rapidly with @xmath59 as @xmath1 increases . that is we have to pay more computational efforts to get a converged situation . on the other side , by increasing @xmath1 the satisfiability probability enhances for smaller values of @xmath59 and gets more rapidly its saturation value . we hope that this behavior of @xmath69 compensate the decrease in @xmath63 for larger problem sizes . as fig . [ f3 ] shows the changes in the quantities are significant and we have a strong size dependence for the small values of @xmath1 studied here . + finally let us look at the statistics of @xmath40 s and the organization of maximum spanning trees in the space spanned by spanning trees . + we observe that if @xmath78 then the weight distribution of the edges , @xmath87 , is almost sum of a few delta peaks . [ f4 ] displays this behavior of @xmath87 for @xmath77 . in both cases , edges of weight @xmath88 have a considerable contribution and the weight distribution dose not define a single characteristic weight . we think that it is these properties of @xmath87 that allow the maximum - spanning - tree scenario to work . a clear difference between the two distributions in fig . [ f4 ] is the presence of a delta peak at @xmath89 for @xmath82 . we found that this peak appears continuously around @xmath90 , where we expect the dynamical phase transition to happen . +    , @xmath18 and @xmath91 when @xmath59 is @xmath92 respectively . the data are result of averaging over @xmath93 realizations , width=302 ]    we define the distance between two spanning trees as the number of uncommon edges . then we take two randomly generated satisfiable spanning trees and obtain their distance @xmath94 . we repeat this for a number of times and construct @xmath95 , the normalized number of times that the two spanning trees are at distance @xmath94 of each other . the result has been shown in fig . [ f5 ] for @xmath96 . in these cases @xmath95 is a gaussian distribution and defines a characteristic distance which grows with @xmath32 . moreover , as the figure displays , by increasing @xmath32 dispersion around the characteristic distance increases . note that more distant factor graphs are more likely to have distant solutions . therefore , we may conclude that as satisfiable spanning trees get away from each other the same happens in the solution space . these facts are consistent with the present picture @xcite of the clustering phenomenon in the solution space . however , the presented data in fig . [ f5 ] are not sufficient to detect the clustering phase transition in the solution space . to this end we should , probably , study the behavior of the average distance and its dispersion for different problem sizes .     for a single realization of random 3-sat problem with @xmath70 and @xmath18 . for @xmath97 ( @xmath98 respectively ) we have generated @xmath99 pairs of satisfiable spanning trees . , width=302 ] we showed that there is a correspondence between the solutions of a random k - sat problem and those of spanning trees in the associated factor graph . this relation may be useful in finding more rigorous results for the structure of the solution space . the concept of null edges helped us to modify survey propagation algorithm and to construct satisfiable spanning trees . a satisfiable spanning tree has a number of solutions ( in the same cluster of solutions ) that can easily be obtained by local search algorithms . this provides us another way of extracting solutions of a random k - sat problem . we used the modified algorithm to study organization of satisfiable spanning trees in the space of spanning trees . we found that by increasing the number of clauses per variable , the distance between satisfiable spanning trees increases . this finding supports the previous results on the clustering in the solution space . + in this paper we focused on the case @xmath100 and @xmath18 but we found that the algorithm works well for @xmath101 and other values of @xmath5 ( not represented here ) .
working with tree graphs is always easier than with loopy ones and spanning trees are the closest tree - like structures to a given graph . 
 we find a correspondence between the solutions of random k - satisfiability problem and those of spanning trees in the associated factor graph . 
 we introduce a modified survey propagation algorithm which returns null edges of the factor graph and helps us to find satisfiable spanning trees . 
 this allows us to study organization of satisfiable spanning trees in the space spanned by spanning trees .