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.

1
vote
0answers
30 views

Mixing time of three particle systems

Is there anything known about mixing time of Markov chains for three particle systems? It is proved here http://www.ams.org/journals/tran/2005-357-08/S0002-9947-05-03610-X/S0002-9947-05-03610-X.pdf ...
1
vote
0answers
34 views

Is this problem in P: Finding a common key for a collection of systems of equations?

Let $B=\{b_1=g_1,\cdots,b_n=g_n\}$ be a set of binary variables $b_i$ and their corresponding values $g_i \in \{0,1\}$. Let $M=\{\sum_{e \in A}e \;:\; A \subset B\}$, i.e., $M$ is the set of all ...
0
votes
1answer
144 views

Problem with the definition of P

In "Introduction to Algorithms: 3rd Edition" there is Theorem 34.2, which states $P = \{ L \mid L \text{ is accepted by a polynomial-time algorithm} \}$ "Accepted in polynomial-time" is defined by:...
0
votes
1answer
248 views

What is an example for a decidable language not in P?

I'm having trouble showing that $P\neq R$. Obviously $P\subseteq R$, but is there a decidable language which is definitely not (under all answers to open questions s.t. $P=NP$ or $NP=PSPACE$) in $P$ ?...
0
votes
1answer
357 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 ...
0
votes
1answer
682 views

If the Clique-k Problem is in P, why not Clique as well?

I have looked at the other answers to this but I still don't get it. (for instance: Why is the clique problem NP-complete?) The general clique problem is defined as $\text{CLIQUE} = \left\{ (G, k) | ...
0
votes
1answer
47 views

Understanding integer factorization is NP [duplicate]

I can see that Integer factorization problem is in NP. I am looking for a simple intuition behind this. For example if we take the problem of sorting the complexity is $n\log n$ for merge/quick sort ...
0
votes
2answers
3k views

Time Complexity of k-clique problem with fixed k [closed]

My question expands on a related question on the link, Why is the clique problem NP-complete? In that post the author argued that while the $k$-clique problem is NP-complete; for a fixed $k$ the $k$-...
0
votes
1answer
75 views

is $x^{100000000000}$ a “polynomial time”?

per this post $t = x^2$ means the problem is solvable in "Polynomial" time. per this post in the form $$a_{n}x^{n}+a_{n-1}x^{n-1}+\dotsb +a_{2}x^{2}+a_{1}x+a_{0} { > \boldsymbol{=0}}$$ ...
0
votes
1answer
470 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?
0
votes
1answer
137 views

Is there a poly-time algorithm for expanding out polynomials

so I've been looking around and haven't seen this before. Basically I'm working with a problem in which I need to expand/FOIL out. Something in the form of $$ z = (x+y)(x-y) \implies x^2+xy-xy+y^2 $$ ...
0
votes
2answers
150 views

approximation algorithm with polynomial complexity

It might be a silly question, I do take a carefully read about approximation algorithm through coursenotes, but when I saw the words "approximation algorithm with polynomial complexity", I can't ...
0
votes
2answers
490 views

How can I prove that there is a decidable language which is not in P?

Generally, I want to use the diagonal argument to prove it. I tried to define a language $A$ which is constructed by a Turing machine $D$: It will only take a input which has a form of a ...
0
votes
1answer
97 views

Time complexity of the fastest algorithm for this case

An array of $n$ distinct elements is said to be un-sorted if for every index $i$ such that $2≤i≤n−1$, either $A[i] > max \{A [i-1], A[i+1]\}$, or$A[i] < min \{A[i-1], A[i+1]\}$. What is the ...
0
votes
1answer
75 views

Relation of deterministic push down automata and lower elementary recursion

Deterministic context free languages are the context free languages that can be accepted by a deterministic push down automata. Deterministic context free languages can be recognized by a ...
0
votes
1answer
462 views

Exponential reduction vs Polynomial Reduction

I'm having trouble understanding reduction. Lets say you have a decision problem A that is NP-Complete. Also, another problem B the can be reduced from A. What can you say about B if: 1) The ...
0
votes
1answer
47 views

Complexity of an encoded turing machine

This is an example of an assignment question, there are 3 of them so I created my own in order to better understand it. First, we have the variable m which is a ...
0
votes
1answer
91 views

Is the spigot algorithm for $\pi$ useful for computing all the digits of $\pi$?

I'm asking the question here because it's not a purely mathematical question and the answer also depends on how computers work. I think that according to the Wikipedia article Bailey–Borwein–Plouffe ...
0
votes
1answer
56 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 ...
0
votes
1answer
236 views

GCD binary representation time complexity

1. Consider the following algorithm for deciding GCD: “On input : ...
0
votes
1answer
87 views

Detemine if two DFA's are non-disjoint in polynomial time?

Given two DFA's , $M_1$ and $M_2$, I want to create an algorithm that determines if their languages are disjoint or not. The algorithm will run in polynomial time. My idea is this: Let's say WLOG ...
0
votes
1answer
122 views

Is the MinMax/optimization/search variant of a decision problem always easier/equal?

Is the MinMax/optimization/search variant of a decision problem always easier/equal in complexity because we can always reduce them to their decision variant? From Wikipedia: If the longest path ...
0
votes
1answer
268 views

Vertex Cover of size k in a tree?

What is a polynomial time algorithm for finding a vertex cover of size $k$ in a tree? Would depth first or breadth first search be efficient or is there some other algorithm that finds the vertex ...
0
votes
0answers
26 views

Is retrospective inference NP-hard?

Here is a minimal working example of the question: Consider a network with nodes arranged in a pyramid: $1$ node in the first row, $1+d$ nodes in the second, $1+2d$ nodes in the third, and so on, ...
0
votes
0answers
26 views

Is the succinct version of P-complete problems out of P?

Consider the succinct versions of the P-complete problems as a Boolean circuit which represents its input in exponential more succinct ways. Could these succinct versions are in P or out of P?
0
votes
1answer
36 views

Sat instance size and definition of TIME(f(n))

Sat usually is defined as the language of a 'reasonable' encoding of satisfable Cnf formulas over n variables. Question: a Cnf formula over n variable with m clauses has a size (as a function of n) ...
0
votes
1answer
70 views

Existence of polynomial time reduction from P to R?

Why the next idea doesn't work: If L_2 in R and L_1 in P and the languages are not trivial, then there is a polynomial-time reduction from L_1 to L_2 I know ...
0
votes
0answers
31 views

USAT, Arora Barak's book

Here on the page 354 Arora and Barak write below the shaded area "but in fact $f(\phi)$ $\notin SAT$" and not "but in fact $f(\phi) \in SAT$" While in the last line of the shaded area they write $...
0
votes
0answers
36 views

How about boolean formula that is satisfied on every reject path and falsified on every accept path of non deterministic Turing machine? [duplicate]

Cook-Levin reduction is both deterministic polynomial time and parsimonious and that's mean that from every non deterministic Turing machine $M$ and string $w$ it is possible in polynomial time ...
0
votes
0answers
65 views

Linear time reduction equivalence

I have to show if the following statement is true or false. Suppose we have two problems $A$ and $B$. We want to know whether the following is true: If $A \le_p B$ and there is an algorithm which ...
0
votes
1answer
41 views

Solve Time Complexity problem using Time Hierarchy

I am trying to understand Time Hierarchy. I have an example that is solvable using the rules of Time Hierarchy. I would like an explanation on how to solve so that I may understand better how to use ...
0
votes
1answer
96 views

Whether the algorithm is polynomial or not with input size which is not polynomial [closed]

A problem may require memory space which is not polynomial with respect to the input size but may still have polynomial run time. Is this true or false? and why? any idea?
0
votes
0answers
104 views

Prove that Vertex Cover belongs to NP

How to prove that the problem VERTEX-COVER belongs to $NP$? The problem VC is defined as follow: INSTANCE: Graph $G = (V,E)$ and an integer $k$ PREDICATE: Is there a subset $V_1 \in V $ s.t $\...
0
votes
0answers
26 views

Revisiting complexity of art gallery-like problem

In a question I had asked earlier, I was interested in knowing whether we could decide in polynomial time whether, for a directed graph $G$ with every one of its vertices belonging to an edge, a size-$...
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
92 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
23 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
219 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
533 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
62 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
62 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
50 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
327 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
84 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
55 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
542 views

Is $P^{SAT[1]}=NP \cup coNP$

I have a following problem: Let $P^{SAT[1]}$ be a class of problems decidable by a deterministic polynomial Turing Machines with SAT oracle. (only one question to oracle). Assume that: $coNP \neq NP ...
-1
votes
1answer
337 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 ...