3 votes

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>...
user avatar
  • 459
2 votes

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 ...
user avatar
  • 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 ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible