# Questions tagged [polynomial-time]

Use for algorithms, algorithm-analysis and complexity-theory questions that aim for polynomial running time resp. time complexity. Such questions often are are reference-requests or about runtime-analysis or time-complexity.

299 questions
Filter by
Sorted by
Tagged with
385 views

### $DTIME(f(n)) \subset of DSPACE(f(n))$

I think this is again an easy one: $DTIME(f(n)) \subset DSPACE(f(n))$ They say its trivial but I dont see it, why? And would $DTIME(f(n^2)) \subset DSPACE(f(n^2))$ also be true? if yes why ...
66 views

### Time complexity for this simple loop

This is the code: j=2 while j<(n*n) j=j*j At first my approach was to treat this like this loop ...
264 views

### NP Class Definition of a Certificate

Given the definition for all x ∈ Σ∗ x ∈ L ⇔ ∃ u ∈ Σ∗ with |u| ≤ p(|x|) and M(x, u) = 1 Lets say the input x = ababab Then the certificate u shouldn't be longer than p(|x|). But what would be p(|...
614 views

### Polynomial-Time Reduction

I have read many resources, but I cannot understand what the polynomial-time reduction is. In everywhere, this is explained with standard-pattern sentences. Please can anyone explain it in detailed ...
256 views

### Time complexity of sum of $2^n$ values of polynomials

First a simpler question: let $q_{1}(k),\dots,q_{n}(k)$ be $n$ polynomials of degree smaller or equal to $n$. Let $f(n): \mathbb{N} \rightarrow \mathbb{N}$ defined by $f(n) = \sum_{i=1}^{n}q_{i}(n)$. ...
116 views

### How to find a minimum spanning forest with a constrained number of nodes in each spanning tree?

Consider a weighted undirected acyclic graph consists of m source (root) vertices and n target vertices. The m-spanning tree problem of the graph is defined as that: (1) each of the m spanning trees ...
34 views

### If a decision problem $A \in \text{NP}$ and there exists reduction so that $A \leq_p B$, for decision problem B, what can be deduced about B?

I think that it implies that B can be solved by a non-deterministic polynomial time or worse Turing machine, but I realise that there is possibly some greater result that I'm missing. Thanks in ...
1k views

### Class P is closed under concatenation

Proving that Class P is closed under concatenation. The answer is given below: But I do not know why stage 2 is repeated at most O(n), could anyone explain this for me please?
250 views

### sequence of problems that take $\Theta(n^k)$ for increasing $k$?

Do we know an infinite sequence of decision problems where the most efficient algorithm for each problem takes $\Theta(n^k)$ time, where $k$ increases unboundedly? Suppose for example that we would ...
45 views

76 views

### If M is recognizing L in polynomial time, is it also deciding it in polynomial time?

Assume that a given turing machine $M$ accepts words in the language in $n^k$ or less steps, but words that aren't in the language are rejected in unknown number of steps (the machine might even ...
76 views

### For any non-trivial $A,B$, finding a language which both are polynomially reducible to

Given two non-trivial (not $\emptyset$ or $\Sigma^*$) languages $A$, $B$ over an alphabet $\Sigma$, which of the following is correct: a. There is a language $C$ such that $A\leq_pC$ and $B\leq_pC$. [....
71 views

### P decision problem that potentially requires at least $\Omega(n \log n)$ in the Turing model?

Currently, it is not proven that $NP \geq O(n \log n)$ in the Turing Machine Model. The weakness of this statement can be illustrated by NP-complete problems, which we think require way more time. ...
86 views

### Is rejecting in polynomial time required for language to be in P?

Language $L$ is in $\mathrm{P}$ if and only if there exists some Turing Machine $M$ such that for every word in $L$, $M$ either accepts or rejects it in polynomial time. Right? But what if all we ...
299 views

### GCD binary representation time complexity

1. Consider the following algorithm for deciding GCD: “On input : ...
204 views

### GOTO vs. including line in loop - will it affect efficiency?

Let's say I have an algorithm something like as follows: ...