By applying a k-sat solver (and finding a solution) we can prove that a k-sat problem is satisfiable. For random 3-sat problems for instance this is expected to happen for m/n < 4.3 (m=nr. of clauses, n=nr. of variables). However, what if m/n > 4.3? In this case we expect that the problem is unsatisfiable but can we also prove it (so we can stop trying to solve it). There are algorithms for this too (although it seems to be a harder problem). Here is an easy one that I got from this website: .
Take a variable X that appears in the largest number of clauses and set it to FALSE. Now all clauses which contain "NOT X" are satisfied and all clauses which contain "X" have 2 variables left. Study the reduced problem with only these reduced 2-variable clauses which is a 2-sat (sub)problem of the original problem. 2-sat is solvable in polynomial time so it is easy to find out if solutions exist (or not), see and your homework Exercise 7.17. If no solutions exist, set "X=TRUE" and repeat. If again no solutions exist than there can be no solutions to the original 3-sat problem. If you cannot prove unsatisfiability for X move on to the next variable etc. If you can't prove unsatisfiability for any variables you fail...
Tuesday, November 2, 2010
Thursday, September 30, 2010
The Ambiguity of Defining Task Environments
Consider a taxi driving agent. This agent is clearly in a multi-agent environment because of the other drivers on the road. They typically prevent the taxi-driver from doing what would be optimal for it (especially when they create a traffic jam). But how about a puzzle solving agent that gets distracted by a bird singing his song? We could argue for both single or multi-agent environments depending on how much the bird irritates the puzzle solving agent.
Another example. Consider a poker playing agent. Poker involves picking cards from a deck. Since these cards are randomly shuffled there seems to be a random element to the game. So is this environment stochastic? It depends. If you model the deck of cards as part of the state space, then the state + the action deterministically determine the next state. However, if the state definition does not involve the order of the deck of cards, then this can be viewed as a random draw which would then argue for a stochastic environment.
Or this example. A part picking robot confronted with a new problem every time can be classified as operating in an episodic environment. However, it may wear in the process or use up battery power in which case it really is sequential.
Chess has a discrete number of states. Or not? If we define a state to be the exact position of every piece on the board then it would be continuous.
Bottom-line: the task environment crucially depends on one's definition of state, action and utility function.
Another example. Consider a poker playing agent. Poker involves picking cards from a deck. Since these cards are randomly shuffled there seems to be a random element to the game. So is this environment stochastic? It depends. If you model the deck of cards as part of the state space, then the state + the action deterministically determine the next state. However, if the state definition does not involve the order of the deck of cards, then this can be viewed as a random draw which would then argue for a stochastic environment.
Or this example. A part picking robot confronted with a new problem every time can be classified as operating in an episodic environment. However, it may wear in the process or use up battery power in which case it really is sequential.
Chess has a discrete number of states. Or not? If we define a state to be the exact position of every piece on the board then it would be continuous.
Bottom-line: the task environment crucially depends on one's definition of state, action and utility function.
Subscribe to:
Posts (Atom)
