Questions tagged [max2sat]
The max2sat tag has no usage guidance.
12
questions
2
votes
0
answers
109
views
Resource on phase transition in MAXCUT problems
Could anyone suggest reading materials on phase transition in MAXCUT problems other than [1]? Thanks.
Ref:
Coppersmith, Don, David Gamarnik, Mohammad Taghi Hajiaghayi, and Gregory B. Sorkin. "...
- 661
1
vote
0
answers
100
views
Software tool to generate the Ising model for random $k$-SAT problems
Is there a software tool available to study the phase transition of the underlying Ising model for a given class of random $k$-SAT problems? I am basically asking whether the framework presented in ...
- 661
1
vote
0
answers
31
views
Clauses structure as quenched random matrix for random $k$-SAT problems
In the Section III of Statistical mechanics of the random K-SAT model, the clauses structure of random $k$-SAT problems are expressed as $M \times N$ quenched random matrix where the numbers of ...
- 661
3
votes
1
answer
86
views
Generating hard satisfiability problems with given constraint graph
Is there a systematic way to tune the hardness of a set of satisfiability problems (say 3-SAT or MAX2SAT) where the constraint graphs are always embeddable into a fixed given graph?
- 661
2
votes
0
answers
38
views
Approximate answer to Max-SMT (bitvector) query
I have a problem that could be completely solved as Max-SMT instances in the theory of quantifier-free bit-vectors, but it apparently is too complex to be tractable with current Max-SMT technology. ...
- 433
2
votes
0
answers
52
views
Complexity class of MCS and relation to #p
I was looking for the complexity class of computing MCS:
Given a boolean formula $\mathcal{F = c_1 \wedge c_2,...,\wedge c_m}$ represented in CNF, a MCS is a subset of the set of clauses $\mathcal{C}$ ...
- 21
7
votes
1
answer
260
views
Number of local maxima in MAX-2-SAT
Given an instance of MAX-2-SAT, let us call an assignment of variables a "local maximum" if changing the value of any variable reduces the number of satisfied clauses. My question is, how many local ...
- 225
4
votes
1
answer
401
views
Balanced Max-2-SAT NP-Hardness
The Balanced Max-2-SAT is a special case of Max-2-SAT (each clause is a disjunction of exactly 2 literals) in which for every variable $x$, there is a $k$ such that $x$ appears positive exactly $k$ ...
- 312
9
votes
2
answers
2k
views
MAX 1 in 2 SAT Algorithm
The maximum satisfiability problem (Max-Sat) is the problem of finding the maximum number of clauses that can be satisified in a Boolean satisfiability instance. The exactly 1 in 2 Sat problem asks, ...
- 639
4
votes
2
answers
1k
views
Greedy MAX SAT approximation ratio
Consider a naive MAX SAT approximation algorithm:
pick a literal $l$ which appears in maximum number of clauses
set the corresponding variable of $l$, such that all clauses containing $l$ are ...
- 57
18
votes
2
answers
730
views
Polynomial time solvable instances of Max-Sat
The problem Max-Sat ask you to find an assignment of a CNF formula which satisfy as many clauses as possible.
For the simpler problem SAT there are many known special cases which can be solved in ...
- 1,349
6
votes
1
answer
1k
views
For what k is MAX-2-SAT-k NP-complete?
It is well-known that it is NP-complete to decide whether in a 2-CNF at least s clauses are satisfiable. It also follows from the reduction from 3-SAT-3 that we can suppose that every literal occurs ...
- 14.1k