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

303 questions
Filter by
Sorted by
Tagged with
176 views

### Methods of turning a decision problem into finding the certificate?

I usually find this in the context of asking about NP-complete problems, but any decision problem works. We start by assuming there's a polynomial time algorithm that gives the yes or no answer. If it'...
94 views

### Characterizing the range of a polytime function

Is it true that an infinite language is in P iff it is the range of a length increasing polytime function? I ask because I know that it is a basic result in computability theory that a set is ...
188 views

49 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 ...
1k 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 ...
555 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}$?
70 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.
52 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: ...
244 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?
128 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 ...
374 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? ...
136 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 ...
255 views

### Polynomial Time Algorithm for Steiner Tree Problem

I know about Steiner Tree Problem. It is stated as Input to Steiner Tree Problem is a weighted graph G and a subset T of the nodes (called terminal nodes) and goal is to find a minimum weight tree ...
44 views

### Are you allowed to change the specifications of a problem when doing reductions?

I'm doing a polynomial time reduction from problem A (known graph problem) to problem B (funky and specific longest path problem). There is a lot of demands on how problem B is supposed to be solved. ...
29 views

### Is there a “well known” example of a constraint satisfaction problem on a 3-element set which is polynomial-time solvable?

I'm basically looking for an example (in maybe graph theory) of a constraint satisfaction problem which has a 3-element set as a domain and the problem is known to be polynomial-time solvable.
261 views

### Complexity of polynomial interpolation

Polynomial Interpolation in the general case is $O(n^2)$ time complexity, but it can be done better in particular situations. For instance, when the polynomial can be evaluated at the complex roots of ...
345 views

### Show that the SAT Problem for CNF formulas with at most two occurences of each variable can be solved in polynomial time

Assuming, I have an arbitrary CNF Formula in which each variable has at most two occurences, how can I proof/show that this can be solved in polynomial time? My first thoughts so far: because each ...
824 views

### Why isn't TQBF part of the polynomial hierarchy?

TQBF consists of alternating quantifiers, so does $\Sigma^2_n$ for fixed $n$. So given a formula in TQBF, shouldn't there be a level of the polynomial hierarchy that solves it? I think this is ...
74 views

### Polynomial Time Reduction - Does 0 calls to the black box still imply a reduction?

Using the following definition: Reduction: There is a polynomial-time reduction from problem $X$ to problem $Y$ if arbitrary instances of problem $X$ can be solved using: Polynomial ...