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

253 questions
542 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 ...
71 views

### Machine with an oracle for a language that cannot decide another language in polynomial time

We usually see examples of languages contained in $P^A$ for some language $A$, or cases where $P^A=P^B$ (or $P^A\subseteq P^B$) for two languages $P^A$ and $P^B$. However, there is any explicit ...
67 views

### Do poly-time algorithms exist whose time complexity is unprovable?

If not, is there a decision procedure that successfully classifies any polynomial time algorithm as poly-time within a time polynomially bounded by the length of the input algorithm?
160 views

### Can one find the minima of a convex function efficiently?

Say I have a real valued convex function $f$ on the hypercube $[-1,1]^n$ and let $f'$ be its restriction on the discrete hypercube $\{-1,1\}^n$. Is there any $poly(n)$ algorithm that for any class of ...
990 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 ...
804 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. ...
974 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? ...
42 views

### Cobham's characterization of FP

Does anyone know of an accessible introduction to Cobham's model independent characterization of FP and it's equivalence to the standard definition using Turing machines? The best source I could find ...
81 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?
263 views

711 views

### Why is it important to solve a problem in Polynomial time, In cryptography?

I have just started to learn Cryptography. I am trying to learn "Merkle-Hellman Knapsack Cryptosystem". So, right at the beginning of the discussion, a question came in my mind: Why is it important ...
492 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 ...
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$-...
276 views

### P-Completeness and Reducibility

I am taking an algorithm analysis class and am stuck on one of my homework problems and would appreciate it if I could receive some guidance. The problem I'm stuck on is proving that the empty ...
12k 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 ...
96 views

### Graph cycles on 40 vertices

I'm trying to create an algorithm in polynomial time, that detects wether or not a graph is in a language. The language specifies that a graph is only part of this language if it has a cycle on 40 ...
261 views

### Algorithm for a special case of SAT/#SAT

Does anyone know of an algorithm that can solve the following special case of SAT in polynomial time? Are there any algorithms that can solve the counting (#SAT) version of it in polynomial time? ...
145 views

### Methods of turning a decision problem into finding the certificate?

I usually find this in the context of asking about NP-complete problems, but any decision problem works. We start by assuming there's a polynomial time algorithm that gives the yes or no answer. If it'...
30 views

### Is it Polynomial to decide whether any product of input numbers satisfies a boolean expression?

I have an input number c of n bits and its prime factorization. I want to find a divisor of c with certain fixed bits "f". For example: ...
87 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 ...
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) ...
122 views

### Common method for solving satisfiability problems which lie in P

I know from Schaefer's Dichotomy Theorem that only a few types of satisfiability problems are in P and any other problem is NP-complete. However, all of the algorithms I know for them use specific ...
53 views

80 views

### Polynomial time algorithms on strings [closed]

I am looking for familiar problems on strings of finite length over an finite alphabet, where a polynomial time algorithm is known. To be more precise, let $\Sigma$ be a finite alphabet. I am looking ...
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)
Using the following definition: Reduction: There is a polynomial-time reduction from problem $X$ to problem $Y$ if arbitrary instances of problem $X$ can be solved using: Polynomial ...