Kyle Jones
  • Member for 9 years, 10 months
  • Last seen this week
  • Seattle, WA
Can there be a perfect chess algorithm?
Accepted answer
13 votes

Your question is akin to the old chestnut: "What happens when an irresistible force meets an immovable object?" The problem is in the question itself: the two entities as described cannot exist in ...

View answer
Using Clique decision to solve Clique optimization
Accepted answer
5 votes

You would use binary search. Start with the lower bound being 3 and the upper bound $n$, where $n$ is the number of vertices. Call your clique decision oracle with a $k$ value halfway between the ...

View answer
How can we reduce variables when converting from 3-SAT to 4-SAT?
2 votes

The paper Effective Preprocessing in SAT through Variable and Clause Elimination covers the variable elimination techniques used in Minisat. Broadly, variables can be eliminated by Substitution, in ...

View answer
Supporting data structures for SAT local search
Accepted answer
9 votes

The needed data structure is an occur list, a list for each variable containing the clauses the variable occurs in. These lists are built once, when the CNF is first read. They are used in steps 3 ...

View answer
Is there a difference between top-down and bottom-up dynamic programming?
31 votes

To use the bottom up method you need to be able to efficiently determine what the "bottom" is, which usually means you need a heavily constrained problem space. If you know what the lowest level ...

View answer
1 2 3 4 5