# CMPS140, Winter 2012, Section 01: Lecture 6

NP-complete.
Note: No finite size problem (like 8-puzzle 15 puzzle) is NP-complete!

NP-hard means at least as hard as NP-complete.
NP-complete means  exponential of possible solutions
that can be each checked in polynomial time.  A large group of problems have been shown to be essentially equivalent incomplexity.

NP-hard problems are probably exponential (not polynomial) in the worst case
but that has never been proven...

For the 8-puzzle, the problem is finding a shortest path solution.
Is there a simple rule?

SATISFIABILITY
===========================================================================
Problem 1:
~(E implies F) and (F or (D implies ~E)). Is this satisfiable?
In conjunctive normal form:
(E) and (~F) and (F or ~D or ~E).  (use relationship p implies q to reduce to.
~p or q, use De Morgans laws and others.)

In boolean matrix (with *s) form: (rows are clauses, columns are variables)
DEF
---
*1*
**0
001

Problem 2:
~((D&E) implies F) and (F or (D implies ~E)). Is this satisfiable?

In conjunctive normal form:
(D) and (E) and (~F) and F or ~D or ~E.

DEF
---
1**
*1*
**0
001

Satisfiability question is whether or not we can find a row of 0 and
1 that matches every other row in one or more places.

In problem 1, YES:010. In problem 2: NO.

NOTE: it is enough to answer the question "yes" or "no"! but
most algorithms (as below) will actually need to find a satisfying assigment to say
"yes".

--------------------------------------------------------

Tradeoff between risk and reward. Generally to achieve higher expected
reward one must take higher risk (standard deviation).

Commitment in search: cutoff one or more potential solutions without
examiningg them.

Aggressive = commital = risky

Conservative = non-committal = not risky

Manhattan Distance for tile puzzles = sum of the distance each
tile is from the goal.

Gaschnig's heuristic = optimal solution length given any tile
can swap with the blank.

Search Algorithms to Look Forward to:

UNINFORMED:  (given legalmove black box, and goalp blackbox).
Uniform-Cost Search
Depth-first search
Depth Bounded
Depth First Iterative Deepening
Bidirectional
INFORMED:  (also given a function h that estimates distance to the goal).
Best-First Search
A*
A*-consistent
Theorems/Proofs  (know basic ideas)

MULTI_AGENT (games)
Minimax
Minimax Alpha-Beta
How computers play chess.