All Questions
Tagged with complexity-theory satisfiability
267 questions
3
votes
1
answer
241
views
Satisfiability where each clause contains almost all variables
Suppose that we have a CNF SAT instance where each clause contains all variables (i.e. in each clause for each variable either the variable or its negation is presented). Such problem can be trivially ...
- 453
0
votes
2
answers
522
views
Definition of SAT Problem [closed]
What is the goal of the SAT Problem?
Check if it is possible to have output '1'?
Above + find the right combination of inputs for that?
Witch one?
Cheers
- 279k
0
votes
1
answer
100
views
What is the complexity of the following problem?
Input: $M$ is non deterministic Turing machine that always halts in $cn^k$ moves/steps, where $c$ and $k$ are constants and $n$ is the length of the input string of $M$, $w$ is any string in $\Sigma^*$...
D.W.♦
- 166k
1
vote
1
answer
141
views
Does exist NP language that is Cook Levin deterministic reducible to xor satisfiability in polynomial time?
We say that the language $L$ is Cook Levin deterministic reducible to xor satisfiability in polynomial time if and only if for each word $w\in\Sigma^*:w\in L\iff f(w)\in XORSAT$ where $\Sigma=\{0,1\}$ ...
CommunityBot
- 1
-1
votes
1
answer
104
views
Relating accepting/rejecting paths to satisfying/falsifying assignments in (Cook, 1971)
I read The Complexity of Theorem-Proving Procedures by Stephen A. Cook (1971).
Cook explains how to create a boolean formula $\Phi$ from $(M,w)$, where $M$ is a non-deterministic Turing machine that ...
- 13.6k
0
votes
1
answer
112
views
If all computations of non deterministic Turing machine on the input string are all accept then is the boolean formula of them a tautology?
If M is non deterministic Turing machine and w is any string then $\Phi_{M,w}$ is satisfiable if and only if M accepts w according to Cook and Levin (1971).
By the definition of non deterministic ...
- 82.2k
1
vote
2
answers
1k
views
P=NP, isn't it?
Cook and Levin showed in 1971 how deterministically in polynomial time from every non deterministic Turing machine M, that halts in polynomial number of moves/steps, and string w to create the boolean ...
CommunityBot
- 1
0
votes
0
answers
38
views
How about boolean formula that is satisfied on every reject path and falsified on every accept path of non deterministic Turing machine? [duplicate]
Cook-Levin reduction is both deterministic polynomial time and parsimonious and that's mean that from every non deterministic Turing machine $M$ and string $w$ it is possible in polynomial time ...
CommunityBot
- 1
0
votes
2
answers
97
views
Does polynomial time reduction from CNFFAL to CNFSAT is also polynomial time reduction from CNFSAT to CNFFAL?
CNFSAT is the language of all strings that are encoding of satisfiable boolean formula in conjunctive normal form while CNFFAL is the language of all strings that are encoding of falsifiable boolean ...
2
votes
1
answer
1k
views
How to proof UNIQUE-SAT is in $\Delta^p_2$
How to proof UNIQUE-SAT is in $\Delta^p_2$ or in $P^{sat}$
1) when given a bool formula can I ask oracle whether the given formula has at least one satisfying truth assignment and whether it has at ...
- 279k
0
votes
0
answers
152
views
Consequences from a lower bound of SAT problem
I'm not sure how lower bounds affect the question to the P=NP problem.
I.e. :
Let a SAT instance with a size of n be transformed into an instance of a problem X with a size of n3.
If you find a ...
- 97
1
vote
1
answer
219
views
Complexity of 1-in-3 SAT variant with restrictions on "unique" variables per clause
I'm interested in the complexity of a particular variant of 1-in-3 SAT. Assume, as is usual, that clauses are allowed to be of length 1, 2, or 3. Then add the restriction that for any clause of length ...
- 453
3
votes
1
answer
227
views
If a CNF contains only Horn and Xor clauses, then what is the complexity of determining Satisfiability?
If a CNF contains only Horn and Xor clauses, and does not contain clauses of other types, then can its Satisfiability be determined in polynomial time?
- 279k
2
votes
1
answer
248
views
What is the complexity of determining Satisfiability of a CNF containing both Horn and Dual Horn clauses?
If a CNF contains both horn and dual horn clauses and does not contain clauses of other types, then can its Satisfiability always be determined in polynomial time?
If the answer to the above problem ...
- 8,149
3
votes
3
answers
1k
views
How does the number of clauses affect the difficulty of a 3-SAT problem? [closed]
What is the relationship between the number of clauses and the difficulty of a 3-SAT problem?
- 31.6k
1
vote
3
answers
162
views
NP-hardness of an extention of 2 sat
a 2 sat instance which is unsatisfiable and an integer k are given, decision problem is that: is it possible to delete k variables, also remove clauses contain them, in order to satisfy the 2-sat ...
- 135
3
votes
2
answers
487
views
Is boolean validity a harder problem than satisfiability?
I am aware that satisfiability is NP complete and unsatisfiability is co-NP complete. But somehow I feel that labeling satisfiability as NP-complete and unsatisfiability as co-NP complete is papering ...
- 30.1k
16
votes
2
answers
1k
views
A dense NP complete language implies P=NP
We say that the language $J \subseteq \Sigma^{*}$ is dense if there exists a polynomial $p$ such that $$ |J^c \cap \Sigma^n| \leq p(n)$$ for all $n \in \mathbb{N}.$ In other words, for any given ...
- 8,149
1
vote
0
answers
147
views
Correct implication for 3SAT from this theorem?
Theorem. Let none of the assignments of length $\log n$ make a set of unsatisfiable 2-clauses. Then formula is satisfiable.
$n$ is input length here.
Let we name an assignment that make the formula ...
- 2,041
1
vote
1
answer
2k
views
Is this possible to solve SAT in polynomial time by reducing it to the problem of solving system of nonlinear equations?
Every conjunctive normal form (CNF) formula can be converted to nonlinear system of equations, where each clause becomes an equation in the system and:
If A and B are logical/boolean variables and ...
- 2,146
3
votes
1
answer
1k
views
3-SAT and Systems of Nonlinear Modular Equations
How is the 3-SAT problem reduced to solving for a system of nonlinear modular equations?
I have read https://stackoverflow.com/questions/4294270/how-to-prove-that-a-problem-is-np-complete in how to ...
- 113
1
vote
1
answer
296
views
MAX-2-XOR-SAT: Why does the special case work?
I'm a new user so I cannot respond directly to this post here.
I'm confused about the answers to the question, namely that MAX-2-XOR-SAT is in $P$ iff each clause is of the form $(x_i \oplus \neg ...
- 11
2
votes
1
answer
556
views
Reduction from 2-SAT to 2-XOR-SAT?
2-SAT is unsatisfiable iff it contains unsatisfiable XOR-2-SAT.
So, first, we just need to combine every clause that contains share same variables (both of them). Then, all of those which remain ...
- 2,041
3
votes
1
answer
985
views
Why is MAX-2SAT not in P?
Max-2-SAT is defined as follows. We are given a 2-CNF formula and a
bound k, and asked to find an assignment to the variables that
satisfies at least k of the clauses.
I can understand the trick ...
- 8,149
0
votes
1
answer
62
views
2
votes
1
answer
2k
views
$NP \ vs \ co-NP$: tautology to SAT and vice versa?
Let define formula $\Phi%$ given in CNF and it's complement $\overline \Phi$.
$\Phi$ is satisfiable iff $\overline \Phi$ is not tautology and vice versa.
$\Phi$ can be converted to $\overline \Phi$ ...
- 8,149
0
votes
0
answers
1k
views
Polynomial Time Reduction: Set Cover to CNF-SAT
How to prove that Set Cover can be polynomial-time reduced to CNF-SAT?
- 1
2
votes
0
answers
107
views
Why does the proof that #SAT is in IP stop after m rounds?
I've been struggling to understand why the interactive proof for #SAT stops after only $m$ rounds, where $m$ is the number of variables in the formula $\phi$. I understand that two polynomials of ...
- 72.9k
8
votes
1
answer
2k
views
Is #HORNSAT polynomial?
A Horn clause is a disjunctive clause of literals containing at most one unnegated literal. Examples are
$$
\neg p \lor \neg r \lor \neg q,\\ \neg s \lor q,\\ \neg s \lor \neg q\lor r,\\ s,\\ \neg r \...
- 956
0
votes
0
answers
306
views
RSA to SAT transform complexity [duplicate]
Is it possible to transform RSA to SAT during polynomial time? (Polynomial number of variables and clauses of logical formula and polynomial time of creating logical formula).
The size of the task is ...
D.W.♦
- 166k
0
votes
2
answers
478
views
Is 2QBF in P^NP?
2QBF is the following problem: given a CNF formula $\psi$ on $2n$ variables, determine the truth value of
$$\forall x \in \{0,1\}^n . \exists y \in \{0,1\}^n . \psi(x,y).$$
Question: Is 2QBF in $P^{...
D.W.♦
- 166k
6
votes
1
answer
4k
views
Simple proof that circuit satisfiability problem is NP-Hard
$\newcommand{\np}{\mathsf{NP}}\newcommand{\cc}{\textrm{Circuit-SAT}}$I am having difficulty understanding the $\np$-hardness proof for $\cc$ in CLRS.
$\cc = \{\langle C \rangle : C \text{ is a ...
CommunityBot
- 1
11
votes
1
answer
580
views
If one shows that UNIQUE k-SAT is in P, does it imply P=NP?
Valiant & Vazirani proved SAT is reducible to UNIQUE SAT under randomized probabilistic reductions in polynomial time. Calabro et al. showed that UNIQUE k-SAT is as hard as k-SAT. Now the ...
- 190
0
votes
1
answer
321
views
Reducing "multiple satisfiability" to normal SAT
I have to prove the NP-completeness of the following set:
QUADRUPLE-SAT:={F is Formula in CNF|F has at least 4 satisfying interpretations}
My idea so far has been to reduce the problem to the normal ...
- 8,149
1
vote
1
answer
107
views
2-clause satisfiability associated graph
A 2-clause is a clause with at most two propositions (clauses?) : $(p \wedge q,\neg p \wedge q, \neg p,...)$. I have to show that the folllowing problem is $\in$ P:
2-SAT:
Input : A conjunction $\Phi$...
CommunityBot
- 1
5
votes
1
answer
467
views
Why is the complement of SAT in IP?
It is mentioned in Sipser's text that the complement of SAT is in $IP$, before $IP$ is formally introduced. After looking at the definition and some of the results, I still don't see why this is the ...
- 1,817
3
votes
1
answer
2k
views
Reducing k Vertex Cover to SAT (last clause problem)
I am working on a transformation from k Vertex Cover to SAT and I have some issues regarding the last clause in the boolean formula.
Here is my approach:
$$\forall \text{ nodes } n_i \in V, \text{...
- 72.9k
0
votes
1
answer
244
views
Is converting boolean formulas to sum-of-products a hard problem?
My reasoning is as follows.
Every boolean formula can be expressed as a sum-of-products.
Every sum-of-produts is a list of minterms.
For each minterm, there is 1 combination of inputs that satisfy ...
CommunityBot
- 1
2
votes
0
answers
408
views
Is Max-2SAT with exactly 3 occurrences per variable APX-hard?
The Max-2SAT problem asks if at least k clauses of a 2CNF formula can be satisfied.
The Max-2SAT(at-most-3) problem is the restriction in which every variable occurs in
at most 3 clauses (counting ...
- 530
2
votes
1
answer
408
views
Reduce the following decision problem to CNF-SAT
Input:
$X$ = {$x_1$,$x_2$,$x_3$,...,$x_n$}
$Y$ = {$y_1$,$y_2$,$y_3$,...,$y_m$}
$k$, where, $k$ $\leq$ $m$
Output (Yes/No):
Satisfying the following condition, can all the elements in set $X$ be ...
- 87
2
votes
1
answer
206
views
Reduction from SAT to shortest cycle?
I have been assigned a homework problem that I cannot figure out:
Prove that SAT has a polynomial-time reduction to the language of undirected non-negative weighted graphs with simple cycle of ...
- 72.9k
2
votes
1
answer
823
views
Reducing MAX-2SAT to Vertex Cover?
In A simplified NP-complete MAXSAT problem, a reduction is given from Min Vertex Cover to MAX-2SAT by replacing each each vertex $x_i$ by a single-variable clause, and each edge by a two-variable ...
- 13.4k
3
votes
1
answer
866
views
Small hard 3-SAT instances
I have read various references that for 3-SAT instances with large numbers of clauses, the optimal clause/variable ratio to generate 'difficult' instances is around 4.
However, I would like to know ...
- 72.9k
1
vote
1
answer
215
views
Upper bound for #Monotone k-SAT
(I've recently started studying satisfiability problems. I've tried to be as clear as possible, but I'm not sure if all of the terminology used is correct.)
Consider a collection of $n$ Boolean ...
CommunityBot
- 1
1
vote
2
answers
560
views
Variation of MAX 3-SAT
Suppose we are given a 3CNF, and we want to know whether k clauses from this 3CNF can be satisfied (k being any natural number)?
I'm trying to think of an efficient algorithm to solve this problem. ...
CommunityBot
- 1
1
vote
1
answer
739
views
Reducing co3SAT to UNIQUE-SAT
I am having trouble with this problem:
Let N3SAT denote the non-satisfiability problem for 3CNF’s. Show that $N3SAT\leq_p
UNQ$ where in UNQ, given a CNF φ we want to know whether there is a unique ...
- 279k
5
votes
1
answer
1k
views
How to show ExactOneSAT is NP-Complete?
$\text{ExactOneSAT}= \{\phi\;|\;\phi\; \text{is a boolean formula}$ $\text{ such that it has a satisfying assignment with only one true literal per clause} \}$
I am trying to reduce 3SAT to this ...
- 4,857
3
votes
1
answer
1k
views
How exactly does a Max 2 Sat reduce to a 3 Sat?
I've been reading this article which tries and explains how the max 2 sat problem is essentially a 3-sat problem and is NP-hard. However, if you see the article, I'm not able to understand why, after <...
- 72.9k
4
votes
1
answer
2k
views
Complexity of 3SAT variants
This question is motivated by my answer to another question in which I stated the fact that both Betweeness and Non-Betweeness problems are $NP$-complete. In the former problem there is a total order ...
CommunityBot
- 1
0
votes
1
answer
977
views
How can you check if a 2SAT problem has a bad loop
im trying to figure out why this is true
The clauses {a,b}, {b,~c}, {c,~a} constitute a 2SAT problem with an implication graph without bad loops.
Can someone show me how to illustrate this and ...
- 198