34 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 ...
D.W.'s user avatar
  • 154k
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, ...
Nathaniel's user avatar
  • 12.3k
23 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 ...
D.W.'s user avatar
  • 154k
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: ...
D.W.'s user avatar
  • 154k
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 ...
Martin Glauer's user avatar
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 ...
D.W.'s user avatar
  • 154k
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). ...
Caleb Stanford's user avatar
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 ...
John L.'s user avatar
  • 38.5k
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 ...
tparker's user avatar
  • 1,034
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.
Tom van der Zanden's user avatar
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$. ...
Denis Pankratov's user avatar
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 ...
Lieuwe Vinkhuijzen's user avatar
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 ...
jmite's user avatar
  • 29.6k
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.
Yuval Filmus's user avatar
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 ...
Steven's user avatar
  • 27.4k
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 ...
Tjaden Hess's user avatar
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 ...
Yuval Filmus's user avatar
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 ...
Yuval Filmus's user avatar
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 ...
Yuval Filmus's user avatar
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 ...
mixdev's user avatar
  • 191
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. ...
ryan's user avatar
  • 4,421
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 ...
Thomas Klimpel's user avatar
8 votes

Why do we say that polynomial time is easy?

I don't think it is possible to argue strictly with only mathematical or theoretical terms. Very much does come down to heuristics. Of course an algorithm with runtime $O(n^{1000})$ or something ...
john_leo's user avatar
  • 1,861
8 votes
Accepted

Do problems in P have a minimum number of YES and NO instances?

If a problem has only "YES" instances (resp. only "NO" instances), then the associated language, which is our formalization of a "problem" contains every word in $\Sigma^*$ (resp. no words), with $\...
Shaull's user avatar
  • 17k
8 votes

Any problem solved by a finite automaton is in P

Yes, this is true. For every such problem there is a DFA that decides the language, and checking if a word is accepted by a DFA can easily be done in time linear in the length of the word.
Pontus's user avatar
  • 687
8 votes
Accepted

Is rejecting in polynomial time required for language to be in P?

Suppose you have a problem $A$, and a TM $M$ which accepts all the words $w \in A$ within a polynomial time bound $p(|w|)$, and diverge (or reject) otherwise. Then, we can craft a new TM $N$, which ...
chi's user avatar
  • 14.4k
8 votes
Accepted

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

In short, if we prove $P=NP$, then we know a whole lot more about computation than we did before, even if we don't find the algorithm, and that was the objective behind research on $P=NP$ all along. ...
Lieuwe Vinkhuijzen's user avatar
8 votes
Accepted

For some $n$, how can we check whether there exists $a,b \in \mathbb{N}$ such that $a^b = n$ in polynomial time?

Note that $b$ is upper bounded by $\log n$, so you can go over all possible integers $x\in\left[1,\lceil\log n\rceil\right]$, and for each $x$ check whether the equation $a^x=n$ has an integer ...
Ariel's user avatar
  • 13.3k
8 votes
Accepted

Proofs of reduction of any hard problem

The first "approach" is the definition of a polynomial time many-one reduction. This is the type of reductions used for defining NP-hardness: a problem $B$ is NP-hard if for every problem $A$...
Yuval Filmus's user avatar
8 votes
Accepted

Determining if an NFA accepts an infinite language in polynomial time

Since $\epsilon$-transitions can be removed in polynomial time, let us assume for simplicity that the NFA does not contain any $\epsilon$-transitions (though the argument can be modified to ...
Yuval Filmus's user avatar

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