3
votes
Accepted
Generating the n-th number with k bits set, is it possible?
This is called Enumerative Coding and was introduced by Tom Cover. Consider a word $W$ that is $n$ bits long, where the one bits are in locations $x_k, \ldots, x_1$ with $x_k>x_{k-1}>\cdots>...
- 459
2
votes
Accepted
If every NP-hard language is PSPACE-hard then NP=PSPACE
"SAT is PSPACE-hard. Since SAT $\in$ NP $\implies \forall L \in$ PSPACE $\leq_{P}$ SAT $\implies$ PSPACE $\subseteq$ NP" is indeed confusing.
What is much clearer is "SAT is PSPACE-HARD ...
- 34.1k
1
vote
Determining whether formula is only satisfied by the all-true assignment
Convert your formula into 3-CNF (not strictly necessary, I think). Duplicate every clause in the formula with new variables and every literal inverted. Then if there exists a satisfying assignment in ...
- 1,024
Only top scored, non community-wiki answers of a minimum length are eligible