# 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 ...
• 162k
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, ...
• 15.8k
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 ...
• 162k
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

### 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). ...
• 7,098
Accepted

• 17.2k

### 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 ...
• 5,400

### 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.
• 687
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 ...
• 14.6k
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. ...
• 4,342
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 ...
• 13.4k
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$...
• 278k
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 ...
• 278k

### Minimum diameter spanning tree problem

The answer is given in the paper that you link to. Specifically, there is a $O(mn+n^2 \log n)$-time algorithm for the problem (with positive edge weights, as required) that works as follows. The ...
• 22.6k
Accepted

### Algorithms that run in polynomial time if P=NP

Wikipedia is describing Levin's universal algorithm. This is an algorithm for verifiable problems, which is competitive with the optimal algorithm (in some sense). In particular, the exact same ...
• 278k
Accepted

### Understanding definition of NP and co-NP

Nondeterministic machines are only allowed to behave nondeterministically in a limited way: very briefly, "Accept iff some branch has [property]" is permitted but "Accept iff no branch has [property]" ...
• 2,818
The time hierarchy theorem says that, for any reasonable function $f$, there are problems that can be decided in time $O(f(n))$ that cannot be decided in time, say, $O(f(n)/n)$. (There are ...
Just extending a bit more what Yuval Filmus has already said. Suppose your input is $x_1\ldots x_n$. Let's use a memorization array $A$, where $A[i]$ is $True$ in case $x_1 \ldots x_i$ is in $L^*$ and ...