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.

Filter by
Sorted by
Tagged with
0
votes
0answers
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" ?
0
votes
0answers
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 ...
0
votes
0answers
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) ...
0
votes
1answer
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. ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
-1
votes
1answer
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 ...
-1
votes
1answer
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 ...
-1
votes
1answer
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)
-1
votes
1answer
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 ...
-1
votes
1answer
343 views

Properties of polynomial time many-one reductions

I'm working on old multiple choice exams and would like to know if the following statements are true or false: a) $L_1 \le_p L_2 \le_p L_3 \Rightarrow L_1 \le_p L_3$ b) If $L \in \mathsf{NP}$ and $U ...
-1
votes
1answer
90 views

How fast can one compute the power of a number?

Let $x \in \mathbb{R}$ and $k \in \mathbb{Z}^+ \cup \{0\}$ then how fast can one compute $x^k$? If $x, k \in \mathbb{Z}$ then I guess this previous discussion already settled that, How many ...
-1
votes
1answer
56 views

A program for polytime languages

Does their exist a program P[m,s] which always halts and for any polytime language exists an m; possibly incomputable; such that P[m,s] accepts only those strings s which are in the language.
-1
votes
1answer
53 views

NXOR for 2 inputs on a turing machine, in P?

Question: L is the language of $\langle M,x,y\rangle$ s.t TM $M$ accepts both inputs $x$ and $y$ or doesn't accept either. Prove that given some $M$, finding 2 inputs $x$ and $y$ s.t. $\langle M,x,y\...
-1
votes
1answer
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 ...
-2
votes
1answer
123 views

Deterministic Random access machine and polynomial time

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$ ...
-2
votes
1answer
289 views

Exponential input and poly-time algorithm

For a list of integers, of size n, where n is exponential, will merge-sort(n), run in poly-time or psuedo poly-time?