All Questions
3 questions
0
votes
1
answer
83
views
n-DNF boolean formula k satisfiability
Given an n variable boolean DNF formula and a number k, does this formula has satisfying input combination greater than k?. (0<=k<=2^n).
Where input is infinite number of n tuples where ...
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
-4
votes
1
answer
234
views
Why is Mixed Quantified Horn SAT in PSPACE?
I want to prove that Mixed Quantified Horn SAT is a PSPACE-complete problem. I have proved that it is PSPACE-hard. How can I prove that it is in PSPACE?
My study:
To prove QSAT to be in PSPACE: ...
- 69