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>...
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 ...
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 ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
reductions × 1186complexity-theory × 559
np-complete × 335
turing-machines × 222
computability × 216
np-hard × 139
undecidability × 124
graphs × 92
np × 90
algorithms × 73
satisfiability × 71
decision-problem × 61
halting-problem × 50
polynomial-time-reductions × 45
polynomial-time × 43
formal-languages × 42
proof-techniques × 37
space-complexity × 29
3-sat × 29
optimization × 27
complexity-classes × 26
time-complexity × 23
semi-decidability × 18
partitions × 18
approximation × 17