# Tag Info

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 ...
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, ...
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 ...
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: ...
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 ...
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). ...
Accepted

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