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

256 questions
Filter by
Sorted by
Tagged with
4answers
13k 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 ...
3answers
38k 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....
2answers
3k 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 ...
1answer
1k views

### Is determining if there is a prime in an interval known to be in P or NP-complete?

I saw from this post on stackoverflow that there are some relatively fast algorithms for sieving an interval of numbers to see if there is a prime in that interval. However, does this mean that the ...
2answers
22k 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 ...
1answer
555 views

### If $n^{\log n}$ is not polynomial or exponential, then what this function is called?

I just found this sentence on page 6 of Garey and Johnson's "Computers and Intractability". Any algorithm whose time complexity function cannot be so bounded is called an exponential time algorithm ...
3answers
2k views

### Problems conjectured but not proven to be easy

We have many problems, like factorization, that are strongly conjectured, but not proven, to be outside P. Are there any questions with the opposite property, namely, that they are strongly ...
2answers
227 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 ...
1answer
1k 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 ...
2answers
805 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. ...
0answers
269 views

### P vs NP and the Time Hierarchy

Assuming $P\neq NP$, is it possible that there exists a $k$ such that $P\subseteq\textsf{NTIME}(t^k)$? There reason I ask this is that I assume the following: P=NP \implies \forall k\ \exists j.\ \...
2answers
1k views

### Any problem solved by a finite automaton is in P

After my Theory of Computation class today this question popped in my mind: If a problem can be solved by a finite automaton, this problem belongs to P. I think its true, since automata recognize ...
3answers
632 views

### Why do most scientists believe that P≠NP?

I read that most scientists don't believe that P=NP. It might be subjective but can you simplify why not? I'm not informed enough to have an opinion but I'd like to know the definitions and some "...
3answers
398 views

### Isn't polynomial identity testing over arithmetic *expressions* trivial?

Polynomial identity testing is the standard example of a problem known to be in co-RP but not known to be in P. Over arithmetic circuits, it does indeed seem hard, since the degree of the polynomial ...
1answer
7k 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?
3answers
423 views

2answers
258 views

### Does P=NP imply polynomial solutions to #P?

Is it true that $\#P$-complete problems could possibly be solved in polynomial time if P=NP? I know that even some counting problems related to polynomial time decision problems are $\#P$-complete, so ...
1answer
398 views

### Complexity of Linear Diophantine equations

My question is simply, can linear Diophantine equations be solved in polynomial time? Specifically, I am looking at equations of the form $a_1 x_1+a_2 x_2 + ... + a_n x_n = k$, where $a_i,x_i,k$ are ...
2answers
617 views

### What is the utility of proving P=NP if we can't find an algorithm that can solve any NP problem in polynomial time?

Here we see a very interesting attempt to show that $\mathrm{P} \ne \mathrm{NP}$ by Norbert Blum. Here we see 116 previous attempts at solving P vs. NP. Here we see the P vs NP problem defined as: ...
2answers
114 views

### Time complexity of art gallery-like problem

Suppose that $G = (V,E)$ is a directed graph such that each vertex in $V$ is in at least one edge in $E$. We'd like to decide whether or not $w$ watchmen can be placed on $w$ distinct vertices in $G$ ...
1answer
590 views

### How do we know for sure that EXPTIME ≠ P?

I'm a beginner in learning about computational complexity and this has stumped me. I've read that by the time hierarchy theorem, it's known that EXP-complete problems are not in P. (Wikipedia) It ...
1answer
205 views

### Finding a perfect matching using an LP

I have a basic question about the power of Linear Programming that has been bothering me for some time. I believe there is something simple I am missing. Linear Programming is $\mathsf{P}$-complete, ...
1answer
3k views

### Are all languages in P?

Are all languages in $\mathbf{P}$? Note: The definitions of all the symbols and functions here follow the document . The following is my attempt to answer the question. Assume that we design a ...
4answers
31k 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 ...
3answers
462 views

### 3SAT analogous problem in P

Is there a problem like 3 SAT like problem in P where if we find an algorithm for this problem, we can solve all problems in P? For instance if we solve this problem in P, may be we can solve prime ...
4answers
2k views

### How can an algorithm have exponential space complexity but polynomial time complexity?

For enumerating the minimal feedback vertex sets of a graph Schwikowski and Speckenmeyer show an algorithm "GENERATE-MFVS" in their publication "On enumerating all minimal solutions of feedback ...
1answer
571 views

### Can we show that non-determinism adds no power, for some specific running time?

$NP = \cup_{k \in \mathbb{N}} NTIME(n^k)$ $P = \cup_{k \in \mathbb{N}} TIME(n^k)$ Can we show that $NTIME(n^k) = TIME(n^k)$ for a specific $k$? For how large of a $k$ can we show the above ...
1answer
1k views

### What is the decidable language in $P/poly$ but not in $P$?

Except for the undecidable unaries I have no idea if there is anything in the gap between $P/poly$ and $P$
2answers
58 views

### Given $k$ points in $n$-dimensions, such that $n\geq3$, is there a polytime algorithm for finding a curve that splits them into 2 sets of points?

So in this math exchange question I asked, it was proven that for $n>2$ dimensions, you can always find a curve that separates $k$ points in $n$-dimensional space into $2$ arbitrary sets that you ...
1answer
501 views

### Polynomial time algorithm for finding two or more vertex-disjoint cycles

The cycle detection problem for a directed graph has well-known polynomial time solutions, graph traversal algorithms such as Dijkstra algorithm can be used to find whether or not a cycle exists in a ...
1answer
181 views

### Proving that a language is not in P using diagonalization

Pardon me if i'm missing something which is very obvious here but i cant seem to figure it out. $E=\{ \langle M, w \rangle \mid \text{ Turing Machine encoded by$M$accepts input$w$after at most$ ...
2answers
158 views

### Implicit complexity and interpretation of total languages

In implicit complexity theory we construct languages that characterize what can be computed in various complexity classes. One major result is Bellantoni and Cook where they show that $FP$ can be ...
1answer
337 views

### Understanding the Sipser-Gacs-Lautemann theorem

The class $BPP$ contains all the languages decided by a probabilistic Turing machine in polynomial time with probability of success more that 2/3 for every input. The class $\Sigma^p_2$ contains all ...
0answers
141 views

2answers
209 views

### “P may collapse” vs. Time hierarchy theorem

https://en.wikipedia.org/wiki/P_versus_NP_problem states: If graph isomorphism is NP-complete, the polynomial time hierarchy collapses to its second level. They further state that this may be ...
1answer
1k views

### Propositional formula in DNF can be decided in polynomial time?

For a given propositional formula f in DNF, one can decide in polynomial time, if the formula is satisfiable: Just walk through all subformulas (l_1 and ... and l_k) and check, wheter it has NO ...
2answers
2k views

### Can the isomorphic graph problem be solved in deterministic polynomial time?

Here is a recent homework problem of mine: Call graphs G and H isomorphic if the nodes of G may be reordered so that it is identical to H. Let ISO = {⟨G,H⟩| G and H are isomorphic graphs}. Show ...