Finally, because each variable only opens the clauses where it appears ( ¬ x only opens clauses that contain ¬ x), to traverse every clause, the player must choose a sequence of variable paths that opens every clause.
Because the avatar only traverses in wires, and a crossover gadget is placed at every intersection, the player must choose an assignment to every variable before reaching the “Check in” and start the clauses’ traversal. Choosing a variable’s value is done by following one of two paths, with no ability to go back due to the one-way gadget. Note that clauses have separate “unlock” and “traverse” paths. The avatar will first visit every variable, choose a value for each one, and open the respective clauses. The avatar’s initial position is “Start”, and the only winning condition must be in “Finish”. The level is created, schematically, according to Figure 2.1.
#Hexcells plus chance how to#
Proof: because 3-CNFSAT is NP-Hard, we only need to show how to reduce from it to the framework, in polynomial time, to prove that it too is NP-Hard. The hardest puzzles will require an exponential number of moves. The optimal sequence is trivial and with an upper bound of O ( board size ) (move the towers alternately, forcing the king to move towards a wall until the edge for a check-mate). Taking the Chess example again, it is easy to find a winning sequence of moves (for Black) if White has only a king and Black has a king and 2 towers.
It is important to note that the complexity of the problem is not tied to any particular instance, but the whole set. Any board configuration is a different instance of the general problem, from the starting configuration with every piece on the board, to the end-game configurations with few pieces left. Consider the game of Chess, where the decision problem is “does Black/White win?”, given a board configuration (size and pieces’ positions) and assuming optimal play from the opponent. An instance is a particular configuration allowed by the problem’s rules. Informally, a problem is the whole set of possible instances.
0 kommentar(er)
