patternMinor
Is FACTORIZATION or PRIMES known to be in LOGSPACE
Viewed 0 times
logspaceprimesknownfactorization
Problem
Are the integer factorization and PRIMES known to be in LOGSPACE?
Recently, it has been shown by researchers that PRIMES is in P. But this does not say anything about LOGSPACE since it is not known if LOGSPACE = P.
Recently, it has been shown by researchers that PRIMES is in P. But this does not say anything about LOGSPACE since it is not known if LOGSPACE = P.
Solution
Factoring is not known to be even in $\mathsf{P}$.
Primality is not known to be in any class conjectured to be smaller than $\mathsf{P}$ (AFAIK).
Primality is not known to be in any class conjectured to be smaller than $\mathsf{P}$ (AFAIK).
Context
StackExchange Computer Science Q#28859, answer score: 7
Revisions (0)
No revisions yet.