# Tag Info

## Hot answers tagged polynomial-time

Accepted

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

No such problem is known (not with a known mathematical proof of a lower bound). Of course cryptographers would jump on it if we had one. As a result, cryptography is currently based on assumptions ...
• 144k

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

The short answer: because you can use Integers to simulate Booleans for SAT, but when you don't restrict yourself to this, then you can't actually simulate SAT. You'll get a feasible answer, but it no ...
• 29.2k
Accepted

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

There is a category of time complexity called quasi-polynomial. It consists of a time complexity of $2^{\mathcal{O}(\log^cn)}$, for $c> 1$. It is asymptoticaly greater than any polynomial function, ...
• 7,534

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

The reason linear programming is "efficient" is that the solution space may be represented by a single convex polyhedron. If one is trying to find the "highest" vertex on that polyhedron (one may ...
• 1,183
Accepted

### Problems conjectured but not proven to be easy

Two decades ago, one of the plausible answers would be primality testing: there were algorithms that ran in randomized polynomial time, and algorithms that ran in deterministic polynomial time under a ...
• 144k
Accepted

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

So your problem is as follows: Input: integers $\ell,u$ Question: does there exist a prime in $[\ell,u]$? As far as I know, it is not known whether that problem is in P or not. Here's what I do know: ...
• 144k
Accepted

### Are all languages in P?

You are misunderstanding how accepting a language works. A language $L$ is in P iff there is a deterministic Turing Machine that decides whether a word $w$ belongs to $L$ in polynomial time. Deciding ...
Accepted

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

What this means is that unary knapsack is in P. It does not mean that knapsack (with binary-encoded numbers) is in P. Knapsack is known to be NP-complete. If you showed that knapsack is in P, that ...
• 144k
Accepted

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

I can't comment since it requires 50 rep, but there are some misconceptions being spread about, especially Raphael's comment "In general, a continous domain means there is no brute force (and no ...
Accepted

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

Yes, it is true. In terms of complexity classes, $$\text{REG} \subseteq \text{P},$$ where $\text{REG}$ is the class of regular languages (i.e., problems that can be solved by a finite automaton). ...
• 5,234

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

Typically, we use $\alpha < 1$ for maximization problems, and $\alpha > 1$ for minimization problems, where $\alpha$ is the approximation guarantee. So, a $2$-approximation algorithm returns a ...
• 22.1k