Timeline for Interactions of number theoretic conjectures and other fields of mathematics
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 5, 2023 at 3:21 | comment | added | Martin Sleziak | The "citeseer" link no longer works - but after changing URL to citeseerx one can see that it was a link to the paper Pascal Koiran: Hilbert's Nullstellensatz is in the Polynomial Hierarchy. | |
| Nov 20, 2013 at 12:38 | comment | added | Lior Silberman | Similarly, polynomials over finite fields can be deterministically factored in polynomial time under GRH; unconditionally only a randomized algorithm is known. | |
| Nov 14, 2013 at 13:42 | comment | added | Emil Jeřábek | While primality testing is in P, there are other examples of similar sort that are unsettled. Square roots modulo primes can be computed in randomized polynomial time by the Tonelli–Shanks algorithm which can be derandomized assuming the GRH, but no unconditional deterministic polynomial-time solution is known. See also arxiv.org/abs/1207.5220 (if I may). | |
| Nov 13, 2013 at 13:43 | comment | added | usul | A straightforward connection is that, if GRH holds, then the Miller-Rabin primality test is correct in deterministic polynomial time. This would have proven the open question "PRIMES in P" ... until the AKS test was discovered and settled the question independently of GRH! | |
| Nov 12, 2013 at 2:51 | history | edited | Daniel Moskovich | CC BY-SA 3.0 |
arthur-merlin inside second level; necessity of GRH unknown to me.
|
| Nov 12, 2013 at 2:12 | comment | added | Noah Schweber | Is it known whether GRH is necessary for of Koiran's result? | |
| S Nov 12, 2013 at 1:52 | history | answered | Daniel Moskovich | CC BY-SA 3.0 | |
| S Nov 12, 2013 at 1:52 | history | made wiki | Post Made Community Wiki by Daniel Moskovich |