What is the Big O of the slowest algorithm in P
December 30, 2006 2:12 PM Subscribe
What is the Big O of the slowest algorithm in P
Essentially I'm trying to understand where the boundary is between P and (not P). Seems like I would want to know this before I tried to decide if P?=NP. My naive way to ask is, for this program:
slowestP(N)
{
K = wtf(N)
for i= 1 to K do
something in constant time
}
what is a definiton for wtf() that describes the largest possible value that would keep this program with a runtime polynomial to N.
So here are two guesses which I'm sure are wrong:
wtf(N) = N^2
wtf(N)= 2^N-1
how would you compute something in between that would define the difference between polynomial and exponential?
I am also not sure about these questions:
Are (P) and (not P) distinct? Are complexity classes sets?
Essentially I'm trying to understand where the boundary is between P and (not P). Seems like I would want to know this before I tried to decide if P?=NP. My naive way to ask is, for this program:
slowestP(N)
{
K = wtf(N)
for i= 1 to K do
something in constant time
}
what is a definiton for wtf() that describes the largest possible value that would keep this program with a runtime polynomial to N.
So here are two guesses which I'm sure are wrong:
wtf(N) = N^2
wtf(N)= 2^N-1
how would you compute something in between that would define the difference between polynomial and exponential?
I am also not sure about these questions:
Are (P) and (not P) distinct? Are complexity classes sets?
It's not exactly a boundary, per se, but wtf(N)=Nm, where m is any finite constant, no matter how large, runs in polynomial time. Even Ngoogleplex is polynomial.
I'm not 100% positive, but I believe wtf(N) is exponential (or of an even higher complexity class) iff, for all finite constants m, the limit of wtf(N)/Nm = ∞ as N → ∞.
posted by DevilsAdvocate at 2:32 PM on December 30, 2006
I'm not 100% positive, but I believe wtf(N) is exponential (or of an even higher complexity class) iff, for all finite constants m, the limit of wtf(N)/Nm = ∞ as N → ∞.
posted by DevilsAdvocate at 2:32 PM on December 30, 2006
Response by poster: clord: No its not homework. So yes, I'd like a specific answer please, if you have one. NlogN is less than N^2, so umm..whats your point?
Devil: Yeah you have the right idea I think, but, is it really ok to say "for all finite constants m"? I mean, I can't plug in "all finite constants m" into any sort of algorithm and have an answer. (wouldnt that beg the defition of constant?) Anyway, as I read your answer, all numerical values of M fit the solution so this definition seems shady to me.
My point here is that if I were to make an algorithm that solved and NP-complete problem in "polynomial" time I want to be sure I know the boundary between "polynomial"and "not polynomial". Looking at the pseudo-polynomial algorithm for subset sum lead me to the question.
Sum[0,0]=True
For S=1 to L do Sum[0, S]= False
For k=1 to n do
For S = 0 to L do
Sum[k, S] = Sum[k-1, S] or Sum[k-1, S - x(k)]
This is polynomial on N, but exponential to the logarithm of L (which is the standard size of a binary representation for numbers). So I asked myself, what would it take to shave this down so it does run polynomial to N, and ran into the issues that I couldnt find a way to correlate L and N with some equation that gave me an upper bound to work with. Like, i could say S=0 to log(L), but there are an unbounded number of ways to make it higher and still be "polynomial"
Thinking about this more I realize im not even sure if complexity classes are actually sets; thus my other questions about P and not P being distinct. Then I got to thinking that if P and not P were not distinct, the question P=NP wouldnt mean anything.
posted by Osmanthus at 3:03 PM on December 30, 2006
Devil: Yeah you have the right idea I think, but, is it really ok to say "for all finite constants m"? I mean, I can't plug in "all finite constants m" into any sort of algorithm and have an answer. (wouldnt that beg the defition of constant?) Anyway, as I read your answer, all numerical values of M fit the solution so this definition seems shady to me.
My point here is that if I were to make an algorithm that solved and NP-complete problem in "polynomial" time I want to be sure I know the boundary between "polynomial"and "not polynomial". Looking at the pseudo-polynomial algorithm for subset sum lead me to the question.
Sum[0,0]=True
For S=1 to L do Sum[0, S]= False
For k=1 to n do
For S = 0 to L do
Sum[k, S] = Sum[k-1, S] or Sum[k-1, S - x(k)]
This is polynomial on N, but exponential to the logarithm of L (which is the standard size of a binary representation for numbers). So I asked myself, what would it take to shave this down so it does run polynomial to N, and ran into the issues that I couldnt find a way to correlate L and N with some equation that gave me an upper bound to work with. Like, i could say S=0 to log(L), but there are an unbounded number of ways to make it higher and still be "polynomial"
Thinking about this more I realize im not even sure if complexity classes are actually sets; thus my other questions about P and not P being distinct. Then I got to thinking that if P and not P were not distinct, the question P=NP wouldnt mean anything.
posted by Osmanthus at 3:03 PM on December 30, 2006
Here are some questions which don't have answers because they don't really make sense: "How many elements are there in the largest finite set?" "Where is the boundary between finite sets and infinite sets?"
These questions don't make sense because there is no largest finite set. Similarly, there is no "slowest polynomial time algorithm."
Of course, the fact that there is no largest finite set doesn't conflict at all with the fact that there is a precise distinction between finite and infinite sets, just as there is a precise distinction between P and (not P).
To sum up: there is a "distinction" but not a "boundary."
By the way, DevilsAdvocate does not have it quite right -- a function like exp(sqrt(N)) grows more quickly than any polynomial, but more slowly than any exponential. Perhaps this "in between" function answers another part of the OP's question.
[Caveat: I promised myself I wouldn't write quick posts about math anymore because they always have mistakes. So please ignore all mistakes in this one, whatever they are.]
posted by escabeche at 3:14 PM on December 30, 2006 [1 favorite]
These questions don't make sense because there is no largest finite set. Similarly, there is no "slowest polynomial time algorithm."
Of course, the fact that there is no largest finite set doesn't conflict at all with the fact that there is a precise distinction between finite and infinite sets, just as there is a precise distinction between P and (not P).
To sum up: there is a "distinction" but not a "boundary."
By the way, DevilsAdvocate does not have it quite right -- a function like exp(sqrt(N)) grows more quickly than any polynomial, but more slowly than any exponential. Perhaps this "in between" function answers another part of the OP's question.
[Caveat: I promised myself I wouldn't write quick posts about math anymore because they always have mistakes. So please ignore all mistakes in this one, whatever they are.]
posted by escabeche at 3:14 PM on December 30, 2006 [1 favorite]
Your question makes no sense. There are Non-polynomial time programs that will run more quickly for a given input then other polynomial problems.
For example, a program with O(n) = n(10100) and another program with a running time O(n) = 2n. The first program is in P, the second program is not, but for any n < 10sup>98, the second program will be faster.
Sounds like homework to me, so i am hopeful you won't get specific answers.
Since it makes no sense, it can't be a homework problem, dumbass.
posted by delmoi at 3:27 PM on December 30, 2006
For example, a program with O(n) = n(10100) and another program with a running time O(n) = 2n. The first program is in P, the second program is not, but for any n < 10sup>98, the second program will be faster.
Sounds like homework to me, so i am hopeful you won't get specific answers.
Since it makes no sense, it can't be a homework problem, dumbass.
posted by delmoi at 3:27 PM on December 30, 2006
I mean, I can't plug in "all finite constants m" into any sort of algorithm and have an answer.
Yes, that's true. A definition of a property is not the same thing as an algorithm for determining whether something has that property. :) I can determine whether wtf(N) is polynomial for many individual definitions of wtf(N), but I don't know of a general algorithm for determining whether wtf(N) is polynomial or exponential (or other).
Anyway, as I read your answer, all numerical values of M fit the solution so this definition seems shady to me.
I'm not following you here. What "solution" are you talking about that M fits?
but exponential to the logarithm of L
exp(log(L)) = L. "Exponential to the logarithm of L" is the same as "linear to L."
To answer your original question another way:
what is a definiton for wtf() that describes the largest possible value that would keep this program with a runtime polynomial to N.
There is no simple definition. Think N100, which is polynomial, might be the largest polynomial time? Nope, N101 is larger. N102 is larger still, but still polynomial. N103 is still yet larger, and still polynomial. Ad infinitum.
On preview: thanks, escabeche! I was trying to think whether there was anything "between" polynomial and exponential, but didn't come up with one in the few minutes it took to write my earlier response. You are, of course, correct. Also, I like your way of describing it: there is a distinction, but not a boundary.
posted by DevilsAdvocate at 3:31 PM on December 30, 2006
Yes, that's true. A definition of a property is not the same thing as an algorithm for determining whether something has that property. :) I can determine whether wtf(N) is polynomial for many individual definitions of wtf(N), but I don't know of a general algorithm for determining whether wtf(N) is polynomial or exponential (or other).
Anyway, as I read your answer, all numerical values of M fit the solution so this definition seems shady to me.
I'm not following you here. What "solution" are you talking about that M fits?
but exponential to the logarithm of L
exp(log(L)) = L. "Exponential to the logarithm of L" is the same as "linear to L."
To answer your original question another way:
what is a definiton for wtf() that describes the largest possible value that would keep this program with a runtime polynomial to N.
There is no simple definition. Think N100, which is polynomial, might be the largest polynomial time? Nope, N101 is larger. N102 is larger still, but still polynomial. N103 is still yet larger, and still polynomial. Ad infinitum.
On preview: thanks, escabeche! I was trying to think whether there was anything "between" polynomial and exponential, but didn't come up with one in the few minutes it took to write my earlier response. You are, of course, correct. Also, I like your way of describing it: there is a distinction, but not a boundary.
posted by DevilsAdvocate at 3:31 PM on December 30, 2006
(Or to be more spesific the answer to your question is O(n) = nX where X is the largest natural number)
posted by delmoi at 3:31 PM on December 30, 2006
posted by delmoi at 3:31 PM on December 30, 2006
Sorry, I didn't read the post fully before posting. It looked like homework to me. I'd like to especially apologize to delmoi, who I have seemed to offend somehow.
posted by clord at 3:34 PM on December 30, 2006
posted by clord at 3:34 PM on December 30, 2006
Sorry, I didn't read the post fully before posting. It looked like homework to me. I'd like to especially apologize to delmoi, who I have seemed to offend somehow.
Well it was an extremely rude comment. Not to derail the thread but "I hope no one answers you" is not a very good answer.
posted by delmoi at 3:44 PM on December 30, 2006
Well it was an extremely rude comment. Not to derail the thread but "I hope no one answers you" is not a very good answer.
posted by delmoi at 3:44 PM on December 30, 2006
I agree, that would be very rude to say.
Anyway, back on topic. My point with the nlogn comment was that you can exceed polynomial growth in BigO notation without resorting to exponential functions.
nx log n, where x is some constant (i.e., non-exponential) value is the first Big-O function which grows faster than O(nx), and it is between O(nx) and O(xn)
My misunderstanding of the question (what made me think it was homework) was that I thought the OP was asking for the first function that is not polymorphic, not the last one which is.
I agree these are different things, and that my comment does not help answer the latter.
posted by clord at 4:03 PM on December 30, 2006
Anyway, back on topic. My point with the nlogn comment was that you can exceed polynomial growth in BigO notation without resorting to exponential functions.
nx log n, where x is some constant (i.e., non-exponential) value is the first Big-O function which grows faster than O(nx), and it is between O(nx) and O(xn)
My misunderstanding of the question (what made me think it was homework) was that I thought the OP was asking for the first function that is not polymorphic, not the last one which is.
I agree these are different things, and that my comment does not help answer the latter.
posted by clord at 4:03 PM on December 30, 2006
Response by poster: escabeche: I like your answer so far the most! I see what you are saying about the distinction between finite and infinite sets, but I'm not sure its the same thing. A finite set of natural numbers is a subset of the infinite set of natural numbers, but P and not P are not subsets of each other, they are supposed to be compliments of each other, something should not be both in P and in not P. Finite and infinite sets may have distinct definitions, but they are not necessarily distinct (by which I mean P intersect not P==null) because for example {1..50} intesect Z == {1..50}.
Also 'finite sets' and 'infinite sets' are not sets, they are types of sets. You could say "all finite sets", but that changes your meaning...wherein isnt P a specific set? (why I ask that question).
I am starting to dribble at the brain of course so bear with me, but I didnt ask for the "slowest polynomial algorithm" I asked for the "Big O" of the slowest polynomial algorithm. Which seems to be a different question altogether.
I guess I'm not convinced that ALL - P = not P, or maybe I'm not sure all functions like exp(sqrt(n)) can be characterized strictly as polynomial or non polynomial, that is to say, is P well defined?
posted by Osmanthus at 4:24 PM on December 30, 2006
Also 'finite sets' and 'infinite sets' are not sets, they are types of sets. You could say "all finite sets", but that changes your meaning...wherein isnt P a specific set? (why I ask that question).
I am starting to dribble at the brain of course so bear with me, but I didnt ask for the "slowest polynomial algorithm" I asked for the "Big O" of the slowest polynomial algorithm. Which seems to be a different question altogether.
I guess I'm not convinced that ALL - P = not P, or maybe I'm not sure all functions like exp(sqrt(n)) can be characterized strictly as polynomial or non polynomial, that is to say, is P well defined?
posted by Osmanthus at 4:24 PM on December 30, 2006
Response by poster: I posted that last after escabeche's first post, didnt read the other posts yet..so .....
posted by Osmanthus at 4:25 PM on December 30, 2006
posted by Osmanthus at 4:25 PM on December 30, 2006
Response by poster: clord: that equation you give is interesting. Now is there a way to encode that in the wtf() function? Also, is there any sort of proof that this is indeed the 'first' function that grows faster than 0(n^x)? Also do you know of a proof that P is well defined?
devil: "but exponential to the logarithm of L " is in fact exactly what I meant. Its part of the confusing part about subsetsum's 'pseudo-polynomial' nature. You see, L is the *value* of the inputs, and is thus *exponential* to the input size (which is encoded into binary bits logL size) which is what we are counting when we measure complexity.
posted by Osmanthus at 4:41 PM on December 30, 2006
devil: "but exponential to the logarithm of L " is in fact exactly what I meant. Its part of the confusing part about subsetsum's 'pseudo-polynomial' nature. You see, L is the *value* of the inputs, and is thus *exponential* to the input size (which is encoded into binary bits logL size) which is what we are counting when we measure complexity.
posted by Osmanthus at 4:41 PM on December 30, 2006
An algorithm is polynomial if it is O(ni) for some constant i. If there is no value of i for which this is true then the algorithm is not polynomial. Realize that the upper bound of big-O is not strict—an algorithm which is O(n) is also O(n2).
However, this is all actually missing the point of the P=NP problem. NP doesn't mean "non-polynomial", it means "non-deterministic polynomial". That's a crucial distinction. "Non-deterministic polynomial" is a class that includes all problems that can be solved in polynomial time if you have a non-determistic Turing machine. A non-deterministic Turing machine is able to always choose the "right" path when branching in an algorithm. Effectively, with non-determinism you get backtracking for free, and so exponential-time algorithms become polynomial-time.
And the problem that is unsolved presently is whether or not non-deterministic polynomial problems can be solved with (perhaps incredibly expensive) deterministic polynomial algorithms. Pretty much everyone thinks the answer is no, but nobody's been able to prove that there's no deterministic, polynomial-time algorithm for the travelling salesman problem or for Boolean satisfiability (SAT).
Once more: NP doesn't mean "non-polynomial", it means "non-deterministic polynomial".
posted by Khalad at 4:51 PM on December 30, 2006 [1 favorite]
However, this is all actually missing the point of the P=NP problem. NP doesn't mean "non-polynomial", it means "non-deterministic polynomial". That's a crucial distinction. "Non-deterministic polynomial" is a class that includes all problems that can be solved in polynomial time if you have a non-determistic Turing machine. A non-deterministic Turing machine is able to always choose the "right" path when branching in an algorithm. Effectively, with non-determinism you get backtracking for free, and so exponential-time algorithms become polynomial-time.
And the problem that is unsolved presently is whether or not non-deterministic polynomial problems can be solved with (perhaps incredibly expensive) deterministic polynomial algorithms. Pretty much everyone thinks the answer is no, but nobody's been able to prove that there's no deterministic, polynomial-time algorithm for the travelling salesman problem or for Boolean satisfiability (SAT).
Once more: NP doesn't mean "non-polynomial", it means "non-deterministic polynomial".
posted by Khalad at 4:51 PM on December 30, 2006 [1 favorite]
Thinking about this more I realize im not even sure if complexity classes are actually sets; thus my other questions about P and not P being distinct. Then I got to thinking that if P and not P were not distinct, the question P=NP wouldnt mean anything.
Yes, they are sets. In fact if the notation could be fixed big-O should really be thought of as dealing with sets as well: n2 ∈ O(n2), and O(n) ⊂ O(n2).
The sets are not distinct. Any problem that is in P is also in NP. What is unproven is if NP is a proper superset of P, that there are problems in NP that are not in P. Most importantly, as far as disjointedness is concerned, is the question of whether P and NP-complete are disjoint sets. We know that the sets are either disjoint or are equal. There is no middle ground, no partial overlap.
For P and NP, though, there is overlap, insofar as every member of P is also a member of NP.
posted by Khalad at 5:10 PM on December 30, 2006
Yes, they are sets. In fact if the notation could be fixed big-O should really be thought of as dealing with sets as well: n2 ∈ O(n2), and O(n) ⊂ O(n2).
The sets are not distinct. Any problem that is in P is also in NP. What is unproven is if NP is a proper superset of P, that there are problems in NP that are not in P. Most importantly, as far as disjointedness is concerned, is the question of whether P and NP-complete are disjoint sets. We know that the sets are either disjoint or are equal. There is no middle ground, no partial overlap.
For P and NP, though, there is overlap, insofar as every member of P is also a member of NP.
posted by Khalad at 5:10 PM on December 30, 2006
Oh, and to answer your second-to-last question: Are (P) and (not P) distinct?
Yes, by definition.
posted by Khalad at 5:11 PM on December 30, 2006
Yes, by definition.
posted by Khalad at 5:11 PM on December 30, 2006
Response by poster: delmoi:Your question makes no sense. Well, perhaps I havent phrased it very well, but the question does make sense; see that clord actually has a damn good stab at an answer so he understood it.
khalad: I have not confused not-P and NP in any way in my posts. That is why I used 'not-P' sometimes, and NP other times. The question, which still isnt perfectly clear to me, is if P is a set that is distinct P = ALL-not P.
posted by Osmanthus at 5:12 PM on December 30, 2006
khalad: I have not confused not-P and NP in any way in my posts. That is why I used 'not-P' sometimes, and NP other times. The question, which still isnt perfectly clear to me, is if P is a set that is distinct P = ALL-not P.
posted by Osmanthus at 5:12 PM on December 30, 2006
Response by poster: Khalad:
Oh, and to answer your second-to-last question: Are (P) and (not P) distinct?
Yes, by definition.
um..no, prove it
posted by Osmanthus at 5:14 PM on December 30, 2006
Oh, and to answer your second-to-last question: Are (P) and (not P) distinct?
Yes, by definition.
um..no, prove it
posted by Osmanthus at 5:14 PM on December 30, 2006
What do you mean by not-P? If you mean {x | x ∉ P} then it is distinct from P, by definition. That's what I thought you meant.
I have not confused not-P and NP in any way in my posts.
Okay, nevermind my first post then. :-)
Here's my working definition of P: {f | ∃i: f ∈ O(ni)}.
And not-P: {f | ¬∃i: f ∈ O(ni)}.
Assuming I got my HTML right, is that what you mean by not-P?
posted by Khalad at 5:24 PM on December 30, 2006
I have not confused not-P and NP in any way in my posts.
Okay, nevermind my first post then. :-)
Here's my working definition of P: {f | ∃i: f ∈ O(ni)}.
And not-P: {f | ¬∃i: f ∈ O(ni)}.
Assuming I got my HTML right, is that what you mean by not-P?
posted by Khalad at 5:24 PM on December 30, 2006
Response by poster: khalad: Well, you use this notation O(n^i),but I've never seen a proof that these things you reference are actually well defined sets and they correspond to algorithm complexity.
This to say I dont see that there is a definite way to determine if a function is in P or not in P.
Devilsadvocate said this:
I can determine whether wtf(N) is polynomial for many individual definitions of wtf(N), but I don't know of a general algorithm for determining whether wtf(N) is polynomial or exponential (or other).
This is the gist of my problem. If there isn't any way to differentiate a 'polynomial' algorithm from an 'exponential' algorithm, maybe its because these are not actually well defined sets.
The point comes down to how does one compare P and NP when one can't even compare P and not P.
posted by Osmanthus at 6:05 PM on December 30, 2006
This to say I dont see that there is a definite way to determine if a function is in P or not in P.
Devilsadvocate said this:
I can determine whether wtf(N) is polynomial for many individual definitions of wtf(N), but I don't know of a general algorithm for determining whether wtf(N) is polynomial or exponential (or other).
This is the gist of my problem. If there isn't any way to differentiate a 'polynomial' algorithm from an 'exponential' algorithm, maybe its because these are not actually well defined sets.
The point comes down to how does one compare P and NP when one can't even compare P and not P.
posted by Osmanthus at 6:05 PM on December 30, 2006
I may be chiming in a bit late here, but if you wanted to define a set P, would it not be possible to say f(n) ∈ P iff ∃ N, k, α > 0 : f(n) < αnsup>k &forall n > N.
Conversely, if there are no such N, k, α > 0, then f is not in P.
posted by claudius at 6:33 PM on December 30, 2006
Conversely, if there are no such N, k, α > 0, then f is not in P.
posted by claudius at 6:33 PM on December 30, 2006
fucker, the HTML didn't work. I meant to say
f(n) ∈ P iff ∃ N, k, α > 0 : f(n) < αnsup>k ∀ n > N
posted by claudius at 6:37 PM on December 30, 2006
f(n) ∈ P iff ∃ N, k, α > 0 : f(n) < αnsup>k ∀ n > N
posted by claudius at 6:37 PM on December 30, 2006
didn't work twice.
it should be:
f(n) ∈ P iff ∃ N, k, α > 0 : f(n) < αn^k/em> ∀ n > N
posted by claudius at 6:38 PM on December 30, 2006
it should be:
f(n) ∈ P iff ∃ N, k, α > 0 : f(n) < αn^k/em> ∀ n > N
posted by claudius at 6:38 PM on December 30, 2006
Here we go...
f(n) ∈ P iff ∃ N, k, α > 0 : f(n) < αnk ∀ n > N
posted by claudius at 6:41 PM on December 30, 2006
f(n) ∈ P iff ∃ N, k, α > 0 : f(n) < αnk ∀ n > N
posted by claudius at 6:41 PM on December 30, 2006
Response by poster: Well I can't read that post claudius, seems like the formatting is messed up.
But let me put it another way, ok so you've defined P, now, you go define E for the definition of exponential then can you prove that P intersect E is null.
posted by Osmanthus at 6:41 PM on December 30, 2006
But let me put it another way, ok so you've defined P, now, you go define E for the definition of exponential then can you prove that P intersect E is null.
posted by Osmanthus at 6:41 PM on December 30, 2006
Well, E is a superset of P since
f(n) ∈ E iff ∃ N, k, α > 0 : f(n) < αenk ∀ n > N
and if f ∈ P then there always exists a greater exponential (you can prove this using the power series expansion of the exponential).
posted by claudius at 6:54 PM on December 30, 2006
f(n) ∈ E iff ∃ N, k, α > 0 : f(n) < αenk ∀ n > N
and if f ∈ P then there always exists a greater exponential (you can prove this using the power series expansion of the exponential).
posted by claudius at 6:54 PM on December 30, 2006
This is the gist of my problem. If there isn't any way to differentiate a 'polynomial' algorithm from an 'exponential' algorithm, maybe its because these are not actually well defined sets.
Claudius gave the formal definition. In English, a function f(x) is polynomial if it is O(ni) for some i, and a function is O(ni) if there exists a value after which g(x)=axi is always bigger than f(x). It's polynomial if there is a polynomial that grows faster than it.
There is no polynomial that grows faster than an exponential function f(x)=ax, so exponential functions are non-polynomial.
In P: sin(x)
Not in P: sin(x) ex — this function doesn't "grow" faster or slower than a polynomial. It's not polynomial, but it's not "bigger" than a polynomial either since it doesn't diverge to a particular limit. There's no boundary that separates functions into "smaller than a polynomial" and "bigger than a polynomial" categories.
posted by Khalad at 7:02 PM on December 30, 2006
Claudius gave the formal definition. In English, a function f(x) is polynomial if it is O(ni) for some i, and a function is O(ni) if there exists a value after which g(x)=axi is always bigger than f(x). It's polynomial if there is a polynomial that grows faster than it.
There is no polynomial that grows faster than an exponential function f(x)=ax, so exponential functions are non-polynomial.
In P: sin(x)
Not in P: sin(x) ex — this function doesn't "grow" faster or slower than a polynomial. It's not polynomial, but it's not "bigger" than a polynomial either since it doesn't diverge to a particular limit. There's no boundary that separates functions into "smaller than a polynomial" and "bigger than a polynomial" categories.
posted by Khalad at 7:02 PM on December 30, 2006
This is the gist of my problem. If there isn't any way to differentiate a 'polynomial' algorithm from an 'exponential' algorithm, maybe its because these are not actually well defined sets.
It isn't necessary for a mathematical object -- such as, say, a class boundary -- to be known in order to know that such an object exists. Set theory is filled with nonconstructive proofs. There are even proofs that certain things that are known to exist can't be constructed.
ok so you've defined P, now, you go define E for the definition of exponential then can you prove that P intersect E is null
I believe what you're looking for is contained in something called the Time Hierarchy Theorem. It is known from this theorem that the complexity class EXP is strictly greater than P. Things like evaluating positions in generalized Chess or Go are EXP-complete (generalized meaning that the game is played on an n-by-n board).
But, notice that you didn't even need to know that to know that Θ(nx) function is in P and a Θ(xn) function is in EXP.
Personally, I have no idea whether a specific function defining the class boundary has been identified. I'll just point you to the Complexity Zoo if you want to look for the answer yourself. Just be aware going in that the precise relationships between many of the over 450 complexity classes identified therein are unknown. So I'd say there's a high probability that you're going to be disappointed if you expect to find what you're asking for, and an even higher probability that you won't find it succinctly stated as you like (since I'm a statistician and not a complexity theorist, this is the only part of my answer that I will state with some authority).
But, for the record, you got the right answer in the second response to this question: a function f(n) is in P iff O(f(n)) = ni for some finite constant i. Just because there is no specific constant i that gives you a fixed upper bound doesn't make this answer wrong. If you insist on identifying a specific constant, you're going to require some bad mathematics, such as that the largest finite constant is 17.
posted by alopez at 7:08 PM on December 30, 2006
It isn't necessary for a mathematical object -- such as, say, a class boundary -- to be known in order to know that such an object exists. Set theory is filled with nonconstructive proofs. There are even proofs that certain things that are known to exist can't be constructed.
ok so you've defined P, now, you go define E for the definition of exponential then can you prove that P intersect E is null
I believe what you're looking for is contained in something called the Time Hierarchy Theorem. It is known from this theorem that the complexity class EXP is strictly greater than P. Things like evaluating positions in generalized Chess or Go are EXP-complete (generalized meaning that the game is played on an n-by-n board).
But, notice that you didn't even need to know that to know that Θ(nx) function is in P and a Θ(xn) function is in EXP.
Personally, I have no idea whether a specific function defining the class boundary has been identified. I'll just point you to the Complexity Zoo if you want to look for the answer yourself. Just be aware going in that the precise relationships between many of the over 450 complexity classes identified therein are unknown. So I'd say there's a high probability that you're going to be disappointed if you expect to find what you're asking for, and an even higher probability that you won't find it succinctly stated as you like (since I'm a statistician and not a complexity theorist, this is the only part of my answer that I will state with some authority).
But, for the record, you got the right answer in the second response to this question: a function f(n) is in P iff O(f(n)) = ni for some finite constant i. Just because there is no specific constant i that gives you a fixed upper bound doesn't make this answer wrong. If you insist on identifying a specific constant, you're going to require some bad mathematics, such as that the largest finite constant is 17.
posted by alopez at 7:08 PM on December 30, 2006
Response by poster: Well what I wanted was not a superset, but a distinct set. There must be a way to determine if a function is in one or the other .
posted by Osmanthus at 7:11 PM on December 30, 2006
posted by Osmanthus at 7:11 PM on December 30, 2006
Osmanthus, perhaps what tripping us up is the definition of P, namely that it includes not only polynomials but also things that are grow slower than polynomials, such as sin(x). From an algebraic point-of-view, sin(x) is not a polynomial. But it is in P.
So when you think of not-P, that set is missing many functions which algebraically-speaking aren't polynomials. The definitions of P (and of E) don't proscribe that the functions in them have to be polynomials or exponentials; they just have to grow no faster than polynomials/exponentials.
Going by the mathematical definition rather than the English description is important here.
posted by Khalad at 7:12 PM on December 30, 2006
So when you think of not-P, that set is missing many functions which algebraically-speaking aren't polynomials. The definitions of P (and of E) don't proscribe that the functions in them have to be polynomials or exponentials; they just have to grow no faster than polynomials/exponentials.
Going by the mathematical definition rather than the English description is important here.
posted by Khalad at 7:12 PM on December 30, 2006
Well what I wanted was not a superset
EXP - P (also known as EXP-complete).
posted by alopez at 7:15 PM on December 30, 2006
EXP - P (also known as EXP-complete).
posted by alopez at 7:15 PM on December 30, 2006
Response by poster: alopez: Yes I have looked at complexity zoo and I have not seen anything specific.
I do understand that a constructive proof may not be possible and yet the definitions can still be sound; its just that if it cannot be constructed then you need to prove that its sound some other way. I will look up the "Time Hierarchy Theorem" and see if this is what I am asking for. It very well may be.
I would say that if the theorem is what I'm looking for, then you have given the best answer.
The second answer doesn't even come close to answering the question in my opinion: its a definition not a proof.
posted by Osmanthus at 7:24 PM on December 30, 2006
I do understand that a constructive proof may not be possible and yet the definitions can still be sound; its just that if it cannot be constructed then you need to prove that its sound some other way. I will look up the "Time Hierarchy Theorem" and see if this is what I am asking for. It very well may be.
I would say that if the theorem is what I'm looking for, then you have given the best answer.
The second answer doesn't even come close to answering the question in my opinion: its a definition not a proof.
posted by Osmanthus at 7:24 PM on December 30, 2006
It is possible to determine if a function is in either P or E - P by finding one of the polynomials that satisfy the definition of P, or by proving that such a polynomial doesn't exist.
If you can find such a polynomial, it's in P (and E), if you can't find a polynomial, but you can find an exponential which satisfies this definition, then it's in E - P (in E but not in P).
If, however, you can't find either a polynomial or an exponential, such as for the function f(n)=nn, then it's not in either set. I would say that this is also in "not-P", since it fails the definition for P.
posted by claudius at 7:33 PM on December 30, 2006
If you can find such a polynomial, it's in P (and E), if you can't find a polynomial, but you can find an exponential which satisfies this definition, then it's in E - P (in E but not in P).
If, however, you can't find either a polynomial or an exponential, such as for the function f(n)=nn, then it's not in either set. I would say that this is also in "not-P", since it fails the definition for P.
posted by claudius at 7:33 PM on December 30, 2006
And when I say "can't find", I mean "can prove not to exist"...
posted by claudius at 7:34 PM on December 30, 2006
posted by claudius at 7:34 PM on December 30, 2006
Boy, this whole discussion is very confusing. I've got to be direct here, Osmanthus, and say that you haven't made it clear yet exactly what your question is.
Re finite and infinite sets -- I think the analogy is sound. If F is the class of finite sets and I the class of countably infinite sets, then F and I are indeed disjoint (that is, F intersect I is empty;) a set cannot be both finite and infinite. I think you are confusing the intersection of sets, which is not relevant here, with the intersection of the classes F and I (where you may think of F as being analogous to P and I to not-P.)
Khalad has it right, but I will reiterate what he said, just because sometimes one has to hear the same thing a few different ways.
P is the set of functions f such that there exists an integer k with f = O(n^k). This is a good, well-formed definition and determines unambiguously whether f is in P.
(not P) is the set of functions f such that there does NOT exist an integer k with f = O(n^k). This is also a good, well-formed definition and determines unambiguously whether f is in (not P).
The phrase "f=O(n^k)" is shorthand for "The function n -> f(n)/n^k is a bounded on the positive integers."
You now have an unambiguous rule which, given a function f, determines whether it is in P, and whether it is in (not-P). It follows immediately from the definitions that every function is either in P or in (not-P), and that no function is in BOTH P and (not-P). (This latter fact can be phrased "P and (not-P) are disjoint" -- I think you are using "distinct" where "disjoint" is more commonly used, but correct me if I'm wrong.)
If this doesn't answer your question, then your question isn't what we all think it is, and you should set us straight!
(P.S. I am teaching this course next semester, so thanks for helping me get warmed up...)
posted by escabeche at 7:49 PM on December 30, 2006
Re finite and infinite sets -- I think the analogy is sound. If F is the class of finite sets and I the class of countably infinite sets, then F and I are indeed disjoint (that is, F intersect I is empty;) a set cannot be both finite and infinite. I think you are confusing the intersection of sets, which is not relevant here, with the intersection of the classes F and I (where you may think of F as being analogous to P and I to not-P.)
Khalad has it right, but I will reiterate what he said, just because sometimes one has to hear the same thing a few different ways.
P is the set of functions f such that there exists an integer k with f = O(n^k). This is a good, well-formed definition and determines unambiguously whether f is in P.
(not P) is the set of functions f such that there does NOT exist an integer k with f = O(n^k). This is also a good, well-formed definition and determines unambiguously whether f is in (not P).
The phrase "f=O(n^k)" is shorthand for "The function n -> f(n)/n^k is a bounded on the positive integers."
You now have an unambiguous rule which, given a function f, determines whether it is in P, and whether it is in (not-P). It follows immediately from the definitions that every function is either in P or in (not-P), and that no function is in BOTH P and (not-P). (This latter fact can be phrased "P and (not-P) are disjoint" -- I think you are using "distinct" where "disjoint" is more commonly used, but correct me if I'm wrong.)
If this doesn't answer your question, then your question isn't what we all think it is, and you should set us straight!
(P.S. I am teaching this course next semester, so thanks for helping me get warmed up...)
posted by escabeche at 7:49 PM on December 30, 2006
And when you're talking about boundaries, you're assuming that the set of complexity classes constitute a topological space (at the least), and therefore the terms "open set" and "closed set" make sense. I don't know the facts of this, but my guess is that if the complexity classes do form a topological space, then E - P would not be a closed set, meaning it would have no boundary.
posted by claudius at 7:49 PM on December 30, 2006
posted by claudius at 7:49 PM on December 30, 2006
Response by poster: I haven't made it clear because, well, I'm not entirely clear on the subject. What I do know is that the most imformative answer so far has been the reference to the Time Heirarchy theorem. This at least purports to prove that P is contained by EXP. One thing I want to point out is that the terminology we are all using is 'fast and loose' and do not actually reflect the strict definitions of complexity classes as they relate to Turing machines.
Take a look at http://www.cs.ubc.ca/~condon/cpsc506/lectures/lec2.pdf and you can see that proving that P is contained by EXP is not a straightforward obvious application of simple mathematical logic. I've got to read this very carefully to understand if it addresses what I am talking about.
I think I'll have to dig deeper though to convince myself that the bare-metal definition of complexity classes really are sets and can actually be 'manipulated' by the symbols we use to manipulate sets. Remember, these things describe algorithms which are finite symbolic entities run on turing machines, so its not at all obvious to me that the theory that describes them is as simple as sets.
The ultimate answer to the answer to how to define WTF() appears to be that there is no answer, but somehow this doesnt sit well with me.
posted by Osmanthus at 9:00 PM on December 30, 2006
Take a look at http://www.cs.ubc.ca/~condon/cpsc506/lectures/lec2.pdf and you can see that proving that P is contained by EXP is not a straightforward obvious application of simple mathematical logic. I've got to read this very carefully to understand if it addresses what I am talking about.
I think I'll have to dig deeper though to convince myself that the bare-metal definition of complexity classes really are sets and can actually be 'manipulated' by the symbols we use to manipulate sets. Remember, these things describe algorithms which are finite symbolic entities run on turing machines, so its not at all obvious to me that the theory that describes them is as simple as sets.
The ultimate answer to the answer to how to define WTF() appears to be that there is no answer, but somehow this doesnt sit well with me.
posted by Osmanthus at 9:00 PM on December 30, 2006
Response by poster: Oh, one other thing, I know my terminology is not perfect, but I do mean something different with 'distinct' than 'disjoint'. Disjoint is something you say about sets, distinct is a question you ask when you suspect these objects are not sets at all.
posted by Osmanthus at 9:20 PM on December 30, 2006
posted by Osmanthus at 9:20 PM on December 30, 2006
Well, as you read and ponder, I urge you to try to write out formal definitions of the concepts you're using. There are various ways to define big-O. I suggest you start with a specific definition in mind and go from there. Formal notation will keep you grounded.
Also, remember, everything can be modeled in terms of sets. ;-)
posted by Khalad at 9:30 PM on December 30, 2006
Also, remember, everything can be modeled in terms of sets. ;-)
posted by Khalad at 9:30 PM on December 30, 2006
(IANAComplexity Theorist.) Things are starting to become clearer; thanks for including that link. It is indeed obvious that P is contained in EXP. What is apparently not obvious is that this containment is proper; i.e. that there are problems in EXP which are not in P. Actually, that fact probably is obvious (though I won't say so confidently, this not being my area) -- but the Time Heirarchy theorem gives a much stronger result, saying, e.g., that there exist problems which can be solved in O(n^2.0001) but not O(n^2).
In any event, I think you've got the right answer about WTF; now the only problem is getting it to "sit well with you." I really think this should not bother you any more than the absence of an answer to "what is the largest integer?" As John von Neumann allegedly used to say, "In mathematics you don't understand things; you just get used to them."
(On preview: whether or not there are any set-theoretic objections to taking P and not-P to be sets, I cannot say; I don't see why there would be, but I would consult a professional...!)
posted by escabeche at 9:34 PM on December 30, 2006
In any event, I think you've got the right answer about WTF; now the only problem is getting it to "sit well with you." I really think this should not bother you any more than the absence of an answer to "what is the largest integer?" As John von Neumann allegedly used to say, "In mathematics you don't understand things; you just get used to them."
(On preview: whether or not there are any set-theoretic objections to taking P and not-P to be sets, I cannot say; I don't see why there would be, but I would consult a professional...!)
posted by escabeche at 9:34 PM on December 30, 2006
Also 'finite sets' and 'infinite sets' are not sets, they are types of sets.
They are sets. Spesifically, they are sets of sets.
I guess I'm not convinced that ALL - P = not P, or maybe I'm not sure all functions like exp(sqrt(n)) can be characterized strictly as polynomial or non polynomial, that is to say, is P well defined?
O(exp(sqrt(n))) is not in P, but is in Exp (exponential time). Everything decidable is in Exp. It's in "not p" because it's not in P. You're terminology is way confused :P
delmoi:Your question makes no sense. Well, perhaps I haven't phrased it very well, but the question does make sense; see that clord actually has a damn good stab at an answer so he understood it.
Well, if you meant NP and not (not P) then it makes a little more sense. But all the O notations of polynomial time algorithms take the form O(ni). So the slowest polynomial time algorithm is the one where I is the largest number possible. But what's the largest number? That's undefined, and so the answer to your question is undefined. That's what I mean when i say it makes no sense, the answer is undefined.
posted by delmoi at 9:49 PM on December 30, 2006
They are sets. Spesifically, they are sets of sets.
I guess I'm not convinced that ALL - P = not P, or maybe I'm not sure all functions like exp(sqrt(n)) can be characterized strictly as polynomial or non polynomial, that is to say, is P well defined?
O(exp(sqrt(n))) is not in P, but is in Exp (exponential time). Everything decidable is in Exp. It's in "not p" because it's not in P. You're terminology is way confused :P
delmoi:Your question makes no sense. Well, perhaps I haven't phrased it very well, but the question does make sense; see that clord actually has a damn good stab at an answer so he understood it.
Well, if you meant NP and not (not P) then it makes a little more sense. But all the O notations of polynomial time algorithms take the form O(ni). So the slowest polynomial time algorithm is the one where I is the largest number possible. But what's the largest number? That's undefined, and so the answer to your question is undefined. That's what I mean when i say it makes no sense, the answer is undefined.
posted by delmoi at 9:49 PM on December 30, 2006
but then you seem to be asking about whats the "boundary" between P and NP, or between P and !P, that's also a question without a good, well defined answer.
posted by delmoi at 9:55 PM on December 30, 2006
posted by delmoi at 9:55 PM on December 30, 2006
Response by poster: First off, NOT everything can be modelled in terms of sets. You can have illformed..things..that violate the axioms of set theory. One reason probably that people are having such a hard time understanding me is that they can't understand what it means that P and (not P) would not be distinct:well, if they are sets, it makes no sense to say this, but if they are not sets, but just ill formed globs of logical goo, then you can come up with all sorts of wacky rules to describe their relationship.
escabeche seems to have caught on when he says : whether or not there are any set-theoretic objections to taking P and not-P to be setss, I cannot say;
What I wonder is have people made too many assumptions about the nature of complexity classes (why DO they call them classes and not complexity sets?) I see all this stuff using set manipulation symbols like union and intersect but I never have actually seen anyone prove that these things are sets that can be operated on in this way.
The idea is (which is probably wrong) is that perhaps one of the reasons we have a such a difficult time struggling with these classes and questions like P=NP is that we have made assumptions about them which are not suficiently precise.
posted by Osmanthus at 10:28 PM on December 30, 2006
escabeche seems to have caught on when he says : whether or not there are any set-theoretic objections to taking P and not-P to be setss, I cannot say;
What I wonder is have people made too many assumptions about the nature of complexity classes (why DO they call them classes and not complexity sets?) I see all this stuff using set manipulation symbols like union and intersect but I never have actually seen anyone prove that these things are sets that can be operated on in this way.
The idea is (which is probably wrong) is that perhaps one of the reasons we have a such a difficult time struggling with these classes and questions like P=NP is that we have made assumptions about them which are not suficiently precise.
posted by Osmanthus at 10:28 PM on December 30, 2006
Best answer: I never have actually seen anyone prove that these things are sets that can be operated on in this way
Well, this is most likely because you're probably most familiar with an algorithmic-style treatment of complexity theory and haven't been exposed to a formal language-theoretic view. Although I am by no means an expert in the field, I'll try to give a brief rundown.
Consider the following: First, let us restrict our attention to deterministic algorithms which take as input a single (finite) binary string and produce as output a single bit, 0 or 1. Since you've mentioned the subset sum problem above, I'll trust that you'll recognize that this is merely a formal way of encoding (deterministic) decision algorithms. For each such algorithm A, we can identify a set of strings which, when fed to A as input, cause A to produce a 1 as output. We call this set of strings LA. We say that LA is the language recognized by A. Note that, LA may be finite or infinite (but only countably so since it consists of only finite strings).
Now, let's flip it around. Let's call any set (finite or infinite) of (finite) binary strings a language. For any language L, we can ask: Does there exist an algorithm A such that L = LA? In fact, we can ask a slightly more interesting question: Does there exist an algorithm A such that L = LA and such that A runs in time bounded by f(n) where n is the length of the input to A and f is some function? If so, we can say informally that L "is" O(f(n)).
Now, we're getting somewhere. Let's define Pk to be the set of languages such that if L is in Pk, then L is O(nk). Recall that a language is a set of strings, so Pk is a set of sets of strings. As a set of languages, we now consider Pk to be a complexity class. However, these classes individually are not really that interesting because for each k < l, Pk is contained in Pl. However, since therse are merely sets, we can take the union over all k=1,2,3,... of the Pk's. This infinite union of sets produces yet another set of languages. We call this set of languages P, which corresponds exactly (unless I've made some blunder) to what we commonly think of as the complexity class P.
Other complexity classes can be similiarly defined (e.g.: for NP, substitute non-deterministic algorithms for deterministic algorithms; for EXP, substitute kn for nk). In the end, complexity classes can be thought of as sets of sets of strings. Questions about complexity class separation (e.g.: is P = NP?) can be thought of as questions about, say, whether the sets of languages underlying these classes are identical or not.
Because this formulation is often incovenient and non-intuitive for lots of people, it isn't often covered very extensively in undergraduate courses. But, it does provide a firm, formal mathematical underpinnining to the whole thing. If you really want to understand these things, I cannot recommend the following two books highly enough:
posted by mhum at 11:59 PM on December 30, 2006 [2 favorites]
Well, this is most likely because you're probably most familiar with an algorithmic-style treatment of complexity theory and haven't been exposed to a formal language-theoretic view. Although I am by no means an expert in the field, I'll try to give a brief rundown.
Consider the following: First, let us restrict our attention to deterministic algorithms which take as input a single (finite) binary string and produce as output a single bit, 0 or 1. Since you've mentioned the subset sum problem above, I'll trust that you'll recognize that this is merely a formal way of encoding (deterministic) decision algorithms. For each such algorithm A, we can identify a set of strings which, when fed to A as input, cause A to produce a 1 as output. We call this set of strings LA. We say that LA is the language recognized by A. Note that, LA may be finite or infinite (but only countably so since it consists of only finite strings).
Now, let's flip it around. Let's call any set (finite or infinite) of (finite) binary strings a language. For any language L, we can ask: Does there exist an algorithm A such that L = LA? In fact, we can ask a slightly more interesting question: Does there exist an algorithm A such that L = LA and such that A runs in time bounded by f(n) where n is the length of the input to A and f is some function? If so, we can say informally that L "is" O(f(n)).
Now, we're getting somewhere. Let's define Pk to be the set of languages such that if L is in Pk, then L is O(nk). Recall that a language is a set of strings, so Pk is a set of sets of strings. As a set of languages, we now consider Pk to be a complexity class. However, these classes individually are not really that interesting because for each k < l, Pk is contained in Pl. However, since therse are merely sets, we can take the union over all k=1,2,3,... of the Pk's. This infinite union of sets produces yet another set of languages. We call this set of languages P, which corresponds exactly (unless I've made some blunder) to what we commonly think of as the complexity class P.
Other complexity classes can be similiarly defined (e.g.: for NP, substitute non-deterministic algorithms for deterministic algorithms; for EXP, substitute kn for nk). In the end, complexity classes can be thought of as sets of sets of strings. Questions about complexity class separation (e.g.: is P = NP?) can be thought of as questions about, say, whether the sets of languages underlying these classes are identical or not.
Because this formulation is often incovenient and non-intuitive for lots of people, it isn't often covered very extensively in undergraduate courses. But, it does provide a firm, formal mathematical underpinnining to the whole thing. If you really want to understand these things, I cannot recommend the following two books highly enough:
- Introduction to Automata Theory, Languages and Computation by Hopcroft & Ullman
- Computers and Intractability: A Guide to the Theory of NP-Completeness by Garey & Johnson
posted by mhum at 11:59 PM on December 30, 2006 [2 favorites]
Man, I always get to these parties late. Yes, P and (not-P) are sets. View algorithms as some subset of all strings. Complexity classes are just sets of algorithms that run in a certain time (definitions given by previous posters). So sets of complexity classes exist, so everything is okay. (i.e. Once you believe that the collection of algorithms is a set, the power set axiom of the ZF system gives you the sets you want. (This is a short version of mhum's post.))
Osmanthus writes "First off, NOT everything can be modelled in terms of sets. You can have illformed..things..that violate the axioms of set theory."
While this is true (e.g. "the set of all sets" cannot exist), set theory does so much that if you want to guess that the problem is assuming things are sets, you'd better give a pretty good reason why. It seems there isn't such a reason, and you now have constructions of these objects using set theory.
Are there any questions you still have about this? Folks have explained a lot of things, so I'm not sure what's still unclear.
posted by samw at 12:47 AM on December 31, 2006
Osmanthus writes "First off, NOT everything can be modelled in terms of sets. You can have illformed..things..that violate the axioms of set theory."
While this is true (e.g. "the set of all sets" cannot exist), set theory does so much that if you want to guess that the problem is assuming things are sets, you'd better give a pretty good reason why. It seems there isn't such a reason, and you now have constructions of these objects using set theory.
Are there any questions you still have about this? Folks have explained a lot of things, so I'm not sure what's still unclear.
posted by samw at 12:47 AM on December 31, 2006
I realized that I neglected to address the original poster's original question. Asking about the slowest algorithm in P would be equivalent to asking whether or not there exists some k such that Pk contains all of P. Or, in other words, if there is some k such that for all l > k, Pk = Pl. However, as pointed out by alopez, the Time Hierarchy Theorem guarantees that P2k is distinct from Pk. If someone were to claim that some language L that was O(nk) was the slowest in P, we could construct a language L' (and yes, the proof of the Time Hierarchy Theorem is constructive) which was O(n2k), thus negating the claim that L was the slowest. (The construction in the Wikipedia link shows that P3k is distinct from Pk, but the idea is the same.)
So, thanks to this theorem, we can say that there is no "slowest algorithm" in P any more than there is a largest natural number.
posted by mhum at 10:34 AM on December 31, 2006
So, thanks to this theorem, we can say that there is no "slowest algorithm" in P any more than there is a largest natural number.
posted by mhum at 10:34 AM on December 31, 2006
This thread is closed to new comments.
consider how fast n ∙ log n will grow. Where does it fit in?
posted by clord at 2:25 PM on December 30, 2006