Russell Easterly
  • Member for 10 years, 9 months
  • Last seen more than 1 year ago
How hard is counting the number of vertex covers after a small perturbation?
2 votes

I describe a method for adding edges to a graph one at a time and computing the number of vertex covers. http://www.mathkb.com/Uwe/Forum.aspx/math/77614/3SAT-A-Better-2SAT-Approximation . Using my ...

View answer
Weighted SAT: is this a known problem?
0 votes

SAT can be converted to Independent Set. Weighted independent set is a well studied problem. A Note on the Approximation of a Minimum Weight Maximal Independent Set

View answer
Complexity of applying a permutation in-place
-2 votes

This method uses the inverse of F and requires n bits of storage. If x is the position of an item in the original array, let G(x) be the position of the item in the sorted array. Let B be an n bit ...

View answer
Complexity of applying a permutation in-place
-2 votes

Any permutation of N items can be converted to any other permutation using N-1 or fewer exchanges. Worst case for this method can require O(n^2) calls to the your oracle, F(). Start from the least ...

View answer