Is P the set of all algorithms whose run-time is $O\left( n^{ O \left( 1 \right) }\right)$? I'm coming to Computer Science from Mathematics and am familiar with the idea of building classes of objects using Propositional Logic. Namely, start with some universe of objects, define some proposition $P \left( x \right)$, and then iterate over the universe of objects, applying $P \left( x \right)$ to each; keep the objects for which $P \left( x \right)$ is true; exclude each object for which $P \left( x \right)$ is false.

So, when we define a class of objects called $\mathbb{P}$ (as in P vs NP), I really need to see a formal definition of the proposition used to build that class--as well as a formal definition of the universe of objects we're starting with.

Defining the Universe of Discourse, $\mathbb{U}$

My understanding is that, for the question of $\mathbb{P}$ vs $\mathbb{NP}$, our universe of discourse is all decision problems that are satisfiable. Namely, problems that can be implemented in boolean logic, return a boolean result, and that someone somewhere at some point has found a finite sequence of inputs that cause the implementation to return $TRUE$.

In spite of Russell's Paradox, let us define our universe of discourse as the set $\mathbb{U}$.

Defining $\mathbb{P}$

$\mathbb{P}$ is a subset of $\mathbb{U}$. Namely, it is the set of all objects in $\mathbb{U}$ for which the following proposition returns $TRUE$:


  This object can be written as a decision problem that returns a boolean value--and that decision problem takes at most $O \left( n^{O \left( 1 \right)} \right)$ time.


That is, given some implementation of a decision problem in $\mathbb{U}$, if that implementation takes at most polynomial time, we can include that implementation in $\mathbb{P}$.

The Point I Need Clarified

Are we really using $O \left( n^{O \left( 1 \right)} \right)$ to define $\mathbb{P}$? Or are we using $\theta \left( n^{O \left( 1 \right)} \right)$? $O \left( n^{O \left( 1 \right)} \right)$ seems right to me, but--so often material I study from doesn't distinguish between Big-O and Big-Theta. So, I need to clarify.

For example, given the following simple, Java-like implementation of an algorithm:

function boolean isOne(int input) {
    return input == 1;
}


Should I include this algorithm in $\mathbb{P}$? It is clearly faster than polynomial time; it is constant time. So, it is $O \left( n^{O \left( 1 \right)} \right)$ but not $\theta \left( n^{O \left( 1 \right)} \right)$--as long as zero $\not\in O \left( 1 \right)$?

Should I include it in $\mathbb{P}$?

If zero $\in O \left( 1 \right)$, then is a constant time algorithm in $\theta \left( n^{O \left( 1 \right)} \right)$?
Should I include this algorithm in $\mathbb{P}$?


Yes. Since the algorithm is asymptotically bounded above by $O(n)$ the algorithm is in $\mathbb{P}$.


  If zero $\in O(1)$, . . .


Zero is in $O(1)$. 


  . . . so often material I study from doesn't distinguish between Big-O and Big-Theta


big-O pertains to an asymptotic upper bound, where big-Theta pertains to an asymptotic tight bound.

The formal definition: $$f(n) \in O(g(n)) \iff \exists N_0,c\in\mathbb{R}^+ \text{ such that } n&gt;N_0 \implies 0 \leq f(n) \leq cg(n)$$ Also, $$f(n) \in \Theta(g(n)) \iff \exists N_0, c_1, c_2 \in \mathbb{R}^+ \text{ such that } n&gt;N_0 \implies c_1g(n)\leq f(n)\leq c_2g(n)$$

For example, $f(n) = n^2 + 3n \in O(n^3)$ and $f(n) \in O(n^2)$. But, $f(n) \not\in \Theta(n^3)$, yet $f(n) \in \Theta(n^2)$. 

We can't use $\Theta(n^{O(1)})$ to describe $\mathbb{P}$, as $O(lg(n))$ isn't in $\Theta(n^{O(1)})$, but is in $O(n^{O(1)})$ (and is in $\mathbb{P}$).