All Questions
2 questions with no upvoted or accepted answers
4
votes
0
answers
311
views
Possible $\mathsf{NP}$ complete problem from number theory
A candidate $\mathsf{NP}$ complete variant of factoring was posted in https://cstheory.stackexchange.com/questions/4769/an-np-complete-variant-of-factoring, where decision problem $\text{BOUNDED-...
- 13.9k
1
vote
0
answers
70
views
Is this factorization problem in EXP?
Factorization is not known to have a polynomial time algorithm. Traditionally the input length is number of bits in representation of the integer to be factored.
However now consider integers of form $...
- 13.9k