# 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>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>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}$).

• I find some things in this answer confusing. An algorithm can not be in P, and neither can $O(lg(n))$ be in P. These are not the right types of objects. – Pontus Apr 20 '17 at 7:11

P is not a set of algorithms, it is a set of languages, where a language is a subset of $\{0, 1\}^*$. In your terminology, the universe of discourse is the power set of $\{0, 1\}^*$ (Russell's paradox is not an issue). P contains exactly those languages $L$ for which there exists a Turing machine $M$ with the following properties.

• When given any $x \in \{0, 1\}^*$ as input, $M$ returns yes if $x \in L$, otherwise it returns no.
• The time complexity function $f_M(n)$ of $M$ is $O(p(n))$ for some polynomial $p$. The time complexity function $f_M(n)$ gives the maximum number of steps for $M$ to halt (with answer yes or no) on any input $x \in \{0, 1\}^*$ such that $n = |x|$.