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.

35 questions
Filter by
Sorted by
Tagged with
3k views

Does two languages being in P imply reduction to each other?

Given two languages $L_1$ and $L_2$ that are in $\mathsf{P}$, can it be proven that there is a polynomial time reduction from $L_1$ to $L_2$ and vice versa? If so, how? I noticed that if $L_1$ is the ...
16k views

Why is linear programming in P but integer programming NP-hard?

Linear programming (LP) is in P and integer programming (IP) is NP-hard. But since computers can only manipulate numbers with finite precision, in practice a computer is using integers for linear ...
4k views

Why not to take the unary representation of numbers in numeric algorithms?

A pseudo-polynomial time algorithm is an algorithm that has polynomial running time on input value (magnitude) but exponential running time on input size(number of bits). For example testing whether ...
11k views

What does the 2 in a 2-approximation algorithm mean?

Does the 2 in a 2-approximation algorithm mean the solution is within 2*OPT or OPT/2?
465 views

Is a “local” version of 3-SAT NP-hard?

Below is my simplification of part of a larger research project on spatial Bayesian networks: Say a variable is "$k$-local" in a string $C \in 3\text{-CNF}$ if there are fewer than $k$ clauses ...
3k views

Can't understand why the DP Subset Sum algorithm is not polynomial

I can not understand why the dynamic programming algorithm for the Subset Sum, is not polynomial. Even though the sum to find 'T' is greater than the total sum of the 'n' elements of the set , the ...
2k views

The running time of the knapsack problem is $O(n\cdot \min(B,V))$ and is not polynomial, why?

My question is why the dynamic programming of the knapsack problem does run in polynomial time? The question is answered here Why is the O(nW) algorithm for the Knapsack problem not a polynomial one? ...
2k views

P is contained in NP ā© Co-NP?

How should I show that ${\sf P}$ is contained in ${\sf NP} \cap {\sf CoNP}$? I.e., all polynomial time solvable problems and their complements are verifiable in polynomial time.
106 views

Polynomial Identity Testing Evaluating a polynomial on a circuit

Say I have a polynomial over $Q$. Let it be given in the form of arithmetic circuit family ${C_n}$. The randomised poly time algorithm evaluates the polynomial at a random point. What if the number of ...
92 views

“Given an algorithm, decide whether it runs in polynomial time” is this problem in NP?

This problem is not decidable (reducible to halting problem) but is semi-decidable and therefor verifiable (as those two definitions are equivalent: How to prove semi-decidable = verifiable?). However,...
46 views

Decide if a string is a member of a language that represents $P$?

For some enumeration of the complexity class P (such as this as an example: How does an enumerator for machines for languages work?), for each string š in the enumeration, does there exist some other ...
60k views

What exactly is polynomial time? [duplicate]

I'm trying to understand algorithm complexity, and a lot of algorithms are classified as polynomial. I couldn't find an exact definition anywhere. I assume it is the complexity that is not exponential....
25k views

Finding shortest and longest paths between two vertices in a DAG

Given an unweighted DAG (directed acyclic graph) $D = (V,A)$ and two vertices $s$ and $t$, is it possible to find the shortest and longest path from $s$ to $t$ in polynomial time? Path lengths are ...
37k views

How to check whether a graph is connected in polynomial time?

I have to solve the following problem: Consider the problem Connected: Input: An unweighted, undirected graph $G$. Output: True if and only if $G$ is connected. Show that Connected ...
4k views

How to prove that problem is not in P

Given some abstract problem how can I prove that this problem is not in P. I mean, what is the method for proving such thesis?
4k views

Show that P is closed against the Kleene star

I have that question that looks kinda easy at first but it is quite hard. Let $L\in P$. Prove that $L^*\in P$ my approach: I tried to generate a Turing machine but I got stuck with the thing of ...
2k views

Does linear programming admit a strongly polynomial-time algorithm?

The linear programming problem: find a strongly-polynomial time algorithm which for given matrix A ā RmĆn and b ā Rm decides whether there exists x ā Rn with Ax ā„ b. I know that Steve Smale's lists ...
887 views

Why do we say that polynomial time is easy? [duplicate]

For years, I've been told (and I've been advocating) that problems which could be solved in polynomial time are "easy". But now I realize that I don't know the exact reason why this is so. ...
7k views

1k views

What is a Turing Machine in class coNP

On the wikipedia article about the polynomial hierarchy http://en.wikipedia.org/wiki/Polynomial_hierarchy it says "$A^B$ is the set of decision problems solvable by a Turing machine in class A ...
117 views

For some $n$, how can we check whether there exists $a,b \in \mathbb{N}$ such that $a^b = n$ in polynomial time?

For some given $n$, how can we check whether there exists $a,b \in \mathbb{N}$ ($b > 0$) such that $a^b = n$ in polynomial time with respect to the number of digits in $n$?
84 views

Suppose P = NC - what then? [duplicate]

Suppose tomorrow someone discovered a proof that P = NC. What would the consequences for computer science research and practical applications be in this case?
542 views

What is the precise definition of pseudo-polynomial time (feat. Counting Sort)

From wikipedia In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the length of the input (the number of bits required ...
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 ...