All Questions
Tagged with complexity-theory satisfiability
267 questions
11
votes
1
answer
852
views
Complexity of deciding if a formula has exactly 1 satisfying assignment
The decision problem
Given a Boolean formula $\phi$, does $\phi$ have exactly one satisfying assignment?
can be seen to be in $\Delta_2$, $\mathsf{UP}$-hard and $\mathsf{coNP}$-hard. Is anything ...
- 4,457
11
votes
1
answer
10k
views
How to prove that a constrained version of 3SAT in which no literal can occur more than once, is solvable in polynomial time?
I'm trying to work out an assignment (taken from the book Algorithms - by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, Chap 8, problem 8.6a), and I'm paraphrasing what it states:
Given that ...
D.W.♦
- 166k
2
votes
1
answer
132
views
Is the following langauge in $P$ or $NPC$
Assuming $P \neq NP$ Is the following langauge in $P$ or $NPC$:
$L=\{\langle\phi\rangle\mid\phi$ is a 3CNF formula with an assignment satisfying at least half of the clauses$\}$
The first thing I ...
- 748
4
votes
1
answer
271
views
Asymptotic bounds on number of 3SAT formulas with unique solutions
A set is sparse if it contains polynomially bounded number of strings of any given string length $n$ otherwise it is dense. All known NP-complete sets are dense. It was proven that P=NP if and only if ...
CommunityBot
- 1
6
votes
2
answers
746
views
Modeling the problem of finding all stable sets of an argumentation framework as SAT
As a continuation of my previous question i will try to explain my problem and how i am trying to convert my algorithm to a problem that can be expressed in a CNF form.
Problem: Find all stable sets ...
CommunityBot
- 1
3
votes
2
answers
204
views
Hardness of finding a true or a false assignment into a generic boolean formula?
I read some research that analyzes the hardness of SAT solving in the average case.
In fact, for a 3CNF formula if you compute the ratio of clause to variables there is an interval (more or less ...
CommunityBot
- 1
8
votes
2
answers
1k
views
Is NAE-HORN-SAT in P or NP-hard?
I am interested to know the complexity of the NAE-HORN-SAT problem
(not all equal). We know that HORNSAT is $\mathsf{P}$-complete, but
on the other hand, NAE-SAT is $\mathsf{NP}$-complete. I want to ...
CommunityBot
- 1
5
votes
1
answer
292
views
Prove that $\text{EXACT-TRIPLE}$ is not in NP
I received the following assignment:
$\text{EXACT-TRIPLE} = \{ \phi \mid \phi \text{ is a boolean formula that has exactly 3 satisfying assignments} \}$.
I need to decide whether this problem ...
- 22.8k
9
votes
2
answers
245
views
Find $\epsilon'$ s.t $L_\epsilon$ is $\mathsf{NP}$-hard for any $\epsilon<\epsilon'$
Let $L_\epsilon$ be the language of all $2$-CNF formulas $\varphi$, such that at least $(\frac{1}{2}+\epsilon)$ of $\varphi$'s clauses can be satisfied.
I need to prove that there exists $\epsilon'$ ...
- 22.5k
5
votes
1
answer
1k
views
How is verifying whether an assignment satisfies a boolean formula possible in polynomial time?
How can I prove that I can verify whether a boolean assignment of variables $a$ satisfies some boolean formmula $\phi$ in polynomial time?
I know that we can just plug the boolean assignment into the ...
- 72.9k
6
votes
1
answer
2k
views
Running time of CDCL compared to DPLL
What's the complexity of Conflict-Driven Clause Learning SAT solvers, compared to DPLL solvers? Was it proven that CDCL is faster in general? Are there instances of SAT that are hard for CDCL but easy ...
- 22.8k
14
votes
2
answers
32k
views
Proving DOUBLE-SAT is NP-complete
The well known SAT problem is defined here for reference sake.
The DOUBLE-SAT problem is defined as
$\qquad \mathsf{DOUBLE\text{-}SAT} = \{\langle\phi\rangle \mid \phi \text{ has at least two ...
- 763
1
vote
0
answers
76
views
How to reduce MaxUNSAT to MaxSAT in a (almost) direct way?
In question How to reduce MaxUNSAT to MaxSAT? I was asking, how to reduce the MaxUNSAT problem to MaxSAT. With help of the given answer I could give a polynomial reduction : $MaxUNSAT \leq ...
CommunityBot
- 1
8
votes
1
answer
443
views
How much can we reduce the number of clauses by converting from $k$-SAT to $(k+m)$-SAT?
If we suppose that we start with an instance of $k$-SAT, and try converting the problem to an instance of $(k+m)$-SAT, where there are $(k+m)$ literals per clause, can we guarantee a reduction in the ...
- 6,221
8
votes
2
answers
1k
views
Is SAT in P if there are exponentially many clauses in the number of variables?
I define a long CNF to contain at least $2^\frac{n}{2}$ clauses, where $n$ is the number of its variables. Let $\text{Long-SAT}=\{\phi: \phi$ is a satisfiable long CNF formula$\}$.
I'd like to know ...
CommunityBot
- 1
4
votes
1
answer
1k
views
Resolution complexity versus a constrained SAT algorithm
EDIT: ad hoc speed-ups are excluded.
We have the result that propositional resolution requires exponential time. The resolution result uses the proof of the pigeonhole principle as an example of a ...
- 22.5k
7
votes
1
answer
16k
views
how do you prove that SAT is NP-complete?
As it is, how do you prove that SAT is NP-complete?
I know what it means by NP-complete, so I do not need an explanation on that.
What I want to know is how do you know that one problem, such as SAT,...
- 72.9k