# 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, v, v} 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.