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

267 questions
Filter by
Sorted by
Tagged with
52 views

### Polynomial Reduction and P [duplicate]

Why w ∈ A if and only if f(w) ∈ B ? Which the signification of "if and only if" ?
95 views

### Are there any RE-complete languages w.r.t. polynomial reduction?

I need to decide if there exists $L\in RE$ so that for every $L'\in RE$ we have $L' \leqslant_p L$, meaning a polynomial-time reduction. I've tried to use $L=A_{TM}$ (the accepting problem), but got ...
24 views

### General methods for polynomial reductions? [duplicate]

Let's say you want to show $A \leq_{p} B$ (this is usually in the context of showing $B$ is NP-complete, but I'm just asking about the reductions. We are specifically looking at polynomial (Karp) ...
239 views

### If A is polynomial time reducible to B such that B <= A, does it mean B must be a polynomial time algorithm?

I don't understand what it means for A to be polynomial time reducible to B. I'm guessing is that we can revised the algorithm some how such that it becomes B, where B is a polynomial time algorithm. ...
598 views

### Proving languages are complete on NL?

I'm trying to prove that every language that is not the empty set or {0,1}* is complete for NL (nondeterministic logarithmic space) under polynomial-time Karp reductions. I'm really not sure how to ...
64 views

### Nash Equilibrium in Tree of Bounded Degree

I have an exercise which I can't solve. Exercise. Consider a game where the players have $2$ pure strategies each and assume that the graph $G$ is a tree with maximum degree $3$. Give a polynomial ...
68 views

### Planar embeddings of planar graph

Let $G=(V,E)$ be a planar graph, only specified by its set of vertices and edges. Suppose $|V|=n$. According to Fary's theorem, there exists a planar embedding of $G$ with straight line segments. Then ...
51 views

### P is closed under power of integer

I'm new in this area of complexity and I'm trying to get into it by understanding basic proofs. I want to prove that if $L\in P$, so $L^k\in P$, where $k$ is non-negative integer. How to prove it in ...
27 views

### polynomial time reduction of 2 langauges

If we can reduce a language y to x. x ≤P y how do I prove x(complement) ≤P y (complement)
2k views

### Proving that the complexity class $P$ is closed under union

The following is my proof for $P$ being closed under union. I wish to know if my proof is correct in addition to what it means for the union of two problems. Proof: Let $p_1, p_2 \in P$ Then by ...
343 views

361 views

### Reducing from Hamiltonian Cycle problem to the Graph Wheel problem cannot be proved vice versa [closed]

I saw a proof by Saeed Amiri, We will add one extra vertex v to the graph G and we make new graph G′, such that v is connected to the all other vertices of G. G has a Hamiltonian cycle if and only if ...
How do we prove $M$ that is a deterministic random access machine that decides a problem $A$ for an input $i$, and $u_M(i)$ is the set of addresses of those registers that occur at least once with $s$ ...