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

43 questions
Filter by
Sorted by
Tagged with
4k 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 ...
19k 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 ...
17k 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?
• 131
87k views

### What exactly is polynomial time?

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....
• 563
5k 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 ...
• 1,357
3k views

### Problems that are polynomially "hard" to compute but "easy" to verify

In the (unlikely) event that $P=NP$ with a constructive proof of a polynomial time algorithm that solves 3SAT, obviously things will be very different. However, practically, it could happen that the ...
• 442
596 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 ...
• 319
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 ...
• 377
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? ...
• 285
3k 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.
1 vote
116 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 ...
• 141
143 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,...
• 315
99 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 ...
• 315
523 views

### Problems that feel exponential but are P

I'm trying to build a list of algorithms/problems that are "exceptionally useful", as in, solving problems that 'seem' very exponential in nature, but have some particularly clever algorithm that ...
• 816
3k views

### Is there an algorithm whose time complexity is between polynomial time and exponential time？

We often hear about some algorithms' running time that is polynomial, and some algorithms' running time that is exponential. But is there an algorithm whose time complexity is between polynomial time ...
• 141
40k 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 ...
• 87
5k 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?
• 143
6k 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 ...
• 712
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 ...
• 234
1k 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. ...
• 101
8k views

• 70.8k
127 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$?
• 457
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 ...
• 406
38 views

### Using the chromatic number to compute an optimal coloring

Suppose we are given a graph $G$ of order $n$ and a black box that can efficiently (polynomial time) compute the chromatic number $\chi(G)$. I am curious to hear how would one go about in order to ...
• 2,420
774 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 ...
• 211
2k views

### If A is in P and B is non-trivial, then A ≤p B [duplicate]

On wikipedia's article on Polynomial-time reduction it states: Every nontrivial decision problem in P (the class of polynomial-time decision problems, where nontrivial means that not every input ...
• 133
1 vote
132 views

### Is longest-path with a specific source and destination impossible in polynomial time?

The problem of finding the longest path in a graph is known to be not be possible in polynomial time, that I am aware of. I am also aware that using DFS or BFS can give the shortest distance between a ...
• 113
1 vote
85 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?
• 793
1 vote
166 views

### Detemine if two DFA's are non-disjoint in polynomial time? [duplicate]

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 ...
• 13