All Questions
Tagged with conjunctive-normal-form computational-complexity
5
questions
3
votes
1
answer
100
views
Prove 20-3-SAT is NP-Complete
so I have this problem that I can't figure out.
20-3-SAT={All satusfiable 3-CNF formulas where each variable appears at most 20 times}
I was able to prove it's in NP using verifier, but for NP-Hard ...
- 189
2
votes
0
answers
286
views
CNF-SAT is NP-complete if and only if CNF-UNSAT is co-NP-complete?
I have shown that a language $A$ is NP-complete $\iff$ its complement $\overline{A}$ is co-NP-complete.
Also, I have shown that CNF-SAT is NP-complete.
Since UNSAT is the complement of SAT, then ...
- 121
1
vote
2
answers
1k
views
CNF unsatisfiability NP-complete?
I have two problems, CNF-SAT and CNF-UNSAT, that decide if a formula $\phi$ on Conjunctive Normal Form is satisfiable and unsatisfiable, respectively. I have already shown that CNF-SAT is $NP$-...
- 121
0
votes
1
answer
3k
views
Reduction from Circuit-Sat to 3-Sat
I'm reading the following notes on reduction from circuit-sat to 3-sat
http://www.cs.cmu.edu/~avrim/451f11/lectures/lect1108.pdf
On the third page i'm unsure how they arrived at the following
In ...
- 1,146
0
votes
1
answer
175
views
Prove NP-Complete. $n$ clubs, largest has $m$ members. Hall Capacity is of $k$ guests. List $k$ students s. t. every club has atleast one member.
Question
Prove that this Problem is $\mathbb{NP-Complete}$ given that that the problem SATISFIABILITY is $\mathbb{NP-Complete}$.
A University has $n$ clubs, the largest of which contains $m$ members (...
- 171