## Algorithm Complexity and Performance

# Algorithm Complexity and Performance

**Bart Massey**

### Example: The Triangle Problem

```
PROBLEM TRIANGLE
Given: An undirected graph G=(V, E).
Question: Is there a "triangle" in G, that is, a set T of
vertices {v[1], v[2], v[3]} in V s.t. all pairs
of vertices in T are edges in E.
```

### The Assumptions Of Big-O

The big-O of an algorithm is independent of the machine it is implemented on.

The scaling at sizes of interest is the big-O scaling.

At least some representative instances scale like big-O.

Lower-order factors don't matter.

Roughly, f(n) in O(n^k) is tractable, others are not.

### Polytime and NP

Difficulty of problem vs complexity of algorithm

Roughly, f(n) in O(n^k) is tractable, others are not.

Some problems are clearly exponential, for example enumerating integers of size n.

### Is it polynomial?

- For some algorithms it's not so obvious whether in O(n^k).
- Consider a problem like NUMBER PARTITIONING: given a set of positive integers with even sum, partition it into two subsets such that the sum of each subset is equal.
- Clearly can
*guess*a right answer and quickly check it: O(|S||max e|). - But is there an algorithm? No one knows.

### NP

NP = Nondeterministic Polynomial: class where guess and check works in polytime

- P=NP? Fundamental CS question
- In practice, assume NP=EXP
- But may solve many large instances with some work

Examples:

- SAT
- Many production scheduling problems
- Rubik's cube and other puzzles

### C Completeness

P is C Complete = P is in C + P is C Hard

P is C Hard = can "reduce" any problem P' in C to P

Reduction: Show that for every instance p' of P', you can

- transform p' into an instance p of P
- use a P-solver to find a solution s of p
- transform s to a solution s' of p'.

### Proving A Problem Is NP-Complete

SAT is in NP: Cook/Karp/Levin ca 1971

Long lists of other NPC problems reduced to SAT, e.g. Garey and Johnson

If you have to do it yourself

- First show that your problem P is in NP: usually easy
- Next, find an existing NPC problem P' that's "close"
- Finally, do the reduction

### Example: BEST TENTMATES

```
PROBLEM BEST TENTMATES
[deriv. MATES by Dennis Sasha, Dr. Dobbs Journal August 1998]
Given: A tent of capacity n. A set P of campers.
A symmetric preference function f : P x P -> {0,1}
indicating which campers "like each other". A
constant h.
Find: A subset P' of P, with |P| <= n, such that
sum(f(c, c') | c, c' in P') is >= h. Everyone
else sleeps outside.
```

### BEST TENTMATES is NPC

Is BEST TENTMATES in NP? Yes, guess and check

- But notice the funny way we rigged the problem
- This is implicitly a
*maximization*: Why? Binary search

Is BEST TENTMATES NP-hard? Yes, by reduction from k-CLIQUE

- Instance of k-CLIQUE is a graph and a k.
- We rig f(v1,v2) = 1 if there is an edge from v1 to v2 and 0 otherwise. Now we build a tent of capacity k and set h = k(k-1)/2.
- Solve BEST TENTMATES instance: if the answer is yes, then the set of vertices in the tent is your k-CLIQUE

### Final Thoughts

Easy to get reduction backwards, with disastrous results

Why do we care? Because it's easy to waste a lot of time trying to find an efficient algorithm for an NP-hard problem.

- For example, Prof. Singh low-power routing problem

Most (all?) of the algorithms we will study in this course are in P. Bleah.