33 votes
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
28 votes

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
27 votes
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
22 votes

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
22 votes
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
20 votes
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
20 votes
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 ...
18 votes
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
17 votes
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 ...
16 votes
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
15 votes

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
14 votes
Accepted

Is a "local" version of 3-SAT NP-hard?

$(3,k)\text{-LSAT}$ is in P for all $k$. As you have indicated, locality is a big obstruction to NP-completeness. Here is a polynomial algorithm. Input: $\phi\in (3,k)\text{-LSAT}$, $\phi=c_1\wedge ...
  • 35.3k
14 votes

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

The general number field sieve, the most efficient known algorithm for factoring large numbers, has a runtime that's roughly $\exp(n^{1/3})$, where $n$ is the number of digits in the number to be ...
  • 984
13 votes
Accepted

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

There is no fixed terminology for these types of functions. You might sometimes see "subexponential" or "superpolynomial" used to refer to this kind of behavior.
13 votes
Accepted

Why is the set of perfect squares in P?

A simple answer is "binary search". Keep track of a lower bound (starts out with 1) and an upper bound (starts out with $n$). In each iteration compute the midpoint $m$. In polytime check if $m∗m=n$. ...
13 votes
Accepted

Does P=NP imply polynomial solutions to #P?

Your confusion is that the class #P only asks you to count the solutions, not to enumerate them, and you only need $n$ bits to write down the number $2^n$. This means that to express the number of ...
12 votes

Problems conjectured but not proven to be easy

It's a tough question, because there isn't a consensus. There are still people who conjecture that $P=NP$. But in my mind, the most notable problem with a significant conjecture that it's in $P$ is ...
  • 29.2k
12 votes
Accepted

Does linear programming admit a strongly polynomial-time algorithm?

This problem is still open. See for example Wikipedia, which while not a dependable source in general, will probably be updated if a strongly polynomial time algorithm is ever found.
11 votes
Accepted

Are there problems in NP that do not reduce in polynomial time to any problem in NP?

I understand the question as asking for the truth value of the proposition $\exists A \in \mathsf{NP}, \forall B \in \mathsf{NP}, A \not\le_p B$, where $\le_p$ denotes Karp reducibility. Then the ...
  • 24.2k
11 votes

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

Other answers have given some specific examples of problems whose difficulty is conjectured to be between polynomial and exponential time, but the Time Hierarchy Theorem gives a general proof that for ...
10 votes
Accepted

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

This algorithm doesn't run in polynomial time, it runs with polynomial delay. As the paper notes: Observe that the number of minimal, and even minimum solutions, can be exponential in the size of ...
10 votes
Accepted

When did polynomial-time algorithm become of interest?

Since this question was reopened and made more explicit, I would like to convert my comment into an answer. Now the OP wants to understand why and when polynomial algorithms became of interest. I ...
  • 9,259
10 votes

Why are most (or all?) polynomial time algorithms practical?

The comment is wrong. It is very easy to give examples of polynomial time algorithms which aren't practical at all: The ellipsoid algorithm for solving linear programs runs in polynomial time but is ...
10 votes
Accepted

Show that P is closed against the Kleene star

Hint: Use dynamic programming. If the input is $x_1 \ldots x_n$, compute inductively whether $x_1 \ldots x_i \in L^*$. Use the fact that you can check whether $x_{j+1} \ldots x_i \in L$ in polynomial ...
9 votes

What exactly is polynomial time?

Running an algorithm can take up some computing time. It mainly depends on how complex the algorithm is. Computer scientists have made a way to classify the algorithm based on its behaviour of how ...
  • 191
9 votes
Accepted

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

If $\mathsf{NTIME}(n^k) \subseteq \mathsf{TIME}(n^\ell)$ for any $k,\ell$ then $\mathsf{P} = \mathsf{NP}$. Indeed, any problem $L \in \mathsf{NP}$ can be solved in non-deterministic time $O(n^r)$ for ...
9 votes

Where/how did a $\log(n)$ factor disappear from well-known algorithms?

You're not wrong, you're just using a different cost model. Typically there are two: Uniform cost model - assigns a constant cost to every machine operation regardless of size of numbers. ...
  • 4,381
8 votes

Complexity of Linear Diophantine equations

Yes, this class of equations can be solved in polynomial time. In particular, there exists a solution if and only $\gcd(a_1,\dots,a_n)$ divides $k$. That condition can be tested in polynomial time, ...
  • 144k
8 votes

Solve parity game in polynomial time?

The state of the art for solving parity games is now quasipolynomial time. Here are references: Deciding Parity Games in Quasipolynomial Time (PDF), by Cristian S. Calude, Sanjay Jain, Bakhadyr ...
8 votes
Accepted

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

Take a language $L$ which is not in $\mathsf{E} = \bigcup_{c=1}^\infty \mathsf{TIME}(2^{cn})$. Now consider the language $L' = \{1^m : m \in L\}$. Then $L'$ is clearly in $\mathsf{P/poly}$, but it's ...

Only top scored, non community-wiki answers of a minimum length are eligible