New answers tagged computational-complexity
3
votes
Problems known to be in both NP and coNP, but not known to be in P
Suppose that $M$ is a triangulated three-manifold. Then deciding if $M$ is homeomorphic to the three-sphere lies in NP and also in co-NP. Its containment in NP is due to Schleimer (see also Ivanov). ...
4
votes
Problems known to be in both NP and coNP, but not known to be in P
This was mentioned in a comment on this answer, but I think it's important enough to warrant its own answer, especially since new results have arisen since then.
A parity game is defined by a directed ...
3
votes
Accepted
References: rigorous algorithms for elementary computations in base-b with complexity estimates
In cryptography, one often needs to implement modular (and polynomial) arithmetic $\mathbb{Z}/N\mathbb{Z}$, but your hardware only natively supports computations in $\mathbb{Z}/n\mathbb{Z}$.
Typical ...
- 2,183
1
vote
Accepted
The equation $ax^2 +by^2 =1 \mod P$ in cyclotomic field
This problem should really be posed over a general finite field (reductions of elements in $\mathcal O_L$ modulo $P$ can be computed in polynomial time).
Over any finite field $F$, the equation $ax^2+...
- 651
7
votes
Accepted
What is the fastest known algorithm for evaluating a homogeneous binary polynomial?
The question does not specify what is meant by “algorithm”, but based on the wording of both questions and the comments, I will assume you want to compute the polynomial by a division-free algebraic ...
- 47.1k
Top 50 recent answers are included