integer_factorization_in_np_cap_conp (412B)
1 # Integer factorization in NP cap coNP 2 3 https://cs.stackexchange.com/questions/52722/why-is-factor-in-co-np 4 5 [integer_factorization] in a certain sense (given m and k, does m have a divisor <k) is in [nptime] cap [conp] 6 - [nptime] for the divisor 7 - [conp] for the [prime_number_decomposition] which can be checked using the fact that [primality_testing] is in [ptime] 8 9 Up: [np_cap_conp], [integer_factorization]