New answers tagged polynomial-time
2
Suppose that $L_1 \in \mathsf{P}$ and $L_2$ is non-trivial. Pick $y \in L_2$ and $z \notin L_2$ arbitrary. The following is a polynomial time reduction from $L_1$ to $L_2$:
Input: $x$.
Check whether $x \in L_1$.
If so, output $y$.
Otherwise, output $z$.
This runs in polynomial time since $L_1 \in \mathsf{P}$.
0
There is already an answer addressing the NTM definition of $\mathbf{NP}$, so let me address the equivalent definition based on proof systems. (For a proof, check your favorite computational complexity textbook.)
$\mathbf{P}$ is the class of problems solvable by a TM in polynomial time (in the length of the input). $\mathbf{NP}$ is the class of problems ...
0
You may want to look at "Adding Multiple Cost Constraints to Combinatorial Optimization Problems, with Applications to Multicommodity Flows" by David Karger and Serge Plotkin (STOC 1995). They find a $(1+\epsilon)$ approximation in ${\tilde O}(\epsilon^{-3}kmn)$ time, where $k$ is the number of commodities, $m$ is the number of edges, and $n$ is the number ...
2
Yes, $x^{100000000000}$ is a polynomial. Your first quote gives an example; your second is the definition.
Top 50 recent answers are included
