# 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.

289 questions
Filter by
Sorted by
Tagged with
188 views

48 views

### Adding the requirement of linear time on infinitely many inputs into the class $P$

Is the following problem computable in polynomial time? Input: $<M_1>$, encoding of a determinstic TM that runs in polynomial time ($L(M_1)\in P$) Output: $<M_2>$, encoding of a ...
989 views

### Question about NP problem certificates and P=NP

From my understanding a problem is considered to be in NP time if it can be solved in polynomial time with a non-deterministic Turing machine and verified in polynomial time with a certificate. My ...
539 views

### On maximum independent set of line graphs

Are there any special algorithms for maximum independent set of line graphs? Could this special case be in $\mathsf{P}$?
69 views

### Is there an example of an oracle A such that P = NP but $\mathsf{P}^A\neq\mathsf{NP}^A$?

The question is stated in the title, I would like to see a counter example if there is any. Thanks.
51 views

### On graph isomorphism over exponential word sizes

Is it known Graph isomorphism can be done in poly time if we allow exponential word sizes? (Shamir's poly time Integer Factoring algorithm is over exponential word sizes).
31 views

### Is it Polynomial to decide whether any product of input numbers satisfies a boolean expression?

I have an input number c of n bits and its prime factorization. I want to find a divisor of c with certain fixed bits "f". For example: ...
235 views

### Proof of P-Hardness by reduction

I want to proof the P-Hardness of a language. Why is it enough to make a reduction-proof from an other, already P-Complete known language?
126 views

### Polynomial Hierarchy — polynomial time TM

Consider, for example, the definition for $\Sigma_2^p$ complexity class. $$x \in L \Leftrightarrow \exists u_1 \forall u_2 \;M(x, u_1, u_2) = 1,$$ where $u_1, u_2 \in \{0,1\}^{p(|x|)}$, for some ...
373 views

### Can you convert a positively weighted DAG into a non-weighted DAG in polynomial time?

Given a positively weighted DAG (directed acyclic graph) $D = (V,E)$, can you create a new non-weighted DAG $D'$ by converting each edge with weight $w(e) = x$ into x non-weighted edges and vertices? ...
122 views

### How undecidable is it whether a given Turing machine runs in polynomial time?

The proof of Theorem 1 that PTime is not semi-decidable in this recent preprint effectively shows that it is $\mathsf{R}\cup\mathsf{coR}$-hard. The proof itself is similar to undecidability proofs at ...
42 views

207 views

### Prove that if a problem L can be decided in polynomial time, then L ≤p L' for any other problem L'

So we know that there exists a Turing Machine $M$ and a polynomial $T$ such that: $M$ halts on all inputs within at most $T(|x|)$ steps If $x$ is in $L$ then $M$ accepts $x$ If $x$ is not in $L$ then ...
27 views

### Is a DTM with k-tapes not the same thing as a NDTM with k-branches?

In the definition of a complexity class like P, where they reference Deterministic Turing machines (DTMs), I don't see any restriction on # of tapes these DTMs are allowed to use. If a language L is ...
44 views

### Are chaotic systems computable in polynomial time

Suppose the parameters/inputs of the computation include the time at which the configuration of a particular deterministic chaotic system needs to be computed. Say, for instance, as input we have a ...
301 views

### Relation beetween log-space reduction and polynomial time reduction

I read somewhere that given two languages A and B, if A <=(log) B, then A <=(P) B (with <=(log) the log-space reduction and <=(P) the polynomial time reduction), but I'm not sure about the ...
237 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)$. ...
65 views

### Defining polynomial hierarchy with oracle machines and quantifiers

While trying to understand the concept of polynomial hierarchy, I noticed that there are several ways to define it. And the most confusing thing about the situation is to see the equivalence between ...
65 views

### On lowness of $\oplus P$

$\oplus P$ is low for itself ($\oplus P^{\oplus P}=\oplus P$). Are there other complexity classes $\mathcal D$ that satisfy $\mathcal D^{\oplus P}=\oplus P$? Are there complexity classes $\mathcal C$ ...
43 views

The definition of the class $UP$ is here. It is of course easy to see that $P\subseteq UP$. I have a problem of proving that there is an oracle $O$ and a language $L$ such that $L\in UP^{\ O}$ but $... 1answer 104 views ### Reduce$SAT$to$3SAT$I was reading this that details a polynomial reduction from$SAT$to$3SAT$. In case$k = 1$or$k = 2$, why don't we just replace those clauses with$C_i' = \{{z_1, y_{i, 1}, y_{i, 2}}\}$and$C_i' =...
Say I have a real valued convex function $f$ on the hypercube $[-1,1]^n$ and let $f'$ be its restriction on the discrete hypercube $\{-1,1\}^n$. Is there any $poly(n)$ algorithm that for any class of ...