New answers tagged

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