All Questions
3
questions
2
votes
0
answers
288
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
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