Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
Visit Stack Exchange
Classical problem which is believed not to be in P is number factoring, which can be cast as checking whethercomputing a decomposition of a cyclic group isinto simple ones.
Several problems in permutation groups are known to be as hard as graph isomorphism, thus not believed to be in P, too.
There are also NP-hard problems known for permutation groups, see e.g. https://www.sciencedirect.com/science/article/pii/S0012365X09001289
Classical problem which is believed not to be in P is number factoring, which can be cast as checking whether a cyclic group is simple.
Several problems in permutation groups are known to be as hard as graph isomorphism, thus not believed to be in P, too.
There are also NP-hard problems known for permutation groups, see e.g. https://www.sciencedirect.com/science/article/pii/S0012365X09001289
Classical problem which is believed not to be in P is number factoring, which can be cast as computing a decomposition of a cyclic group into simple ones.
Several problems in permutation groups are known to be as hard as graph isomorphism, thus not believed to be in P, too.
There are also NP-hard problems known for permutation groups, see e.g. https://www.sciencedirect.com/science/article/pii/S0012365X09001289
Classical problem which is believed not to be in P is number factoring, which can be cast as checking whether a cyclic group is simple.
Several problems in permutation groups are known to be as hard as graph isomorphism, thus not believed to be in P, too.
There are also NP-hard problems known for permutation groups, see e.g. https://www.sciencedirect.com/science/article/pii/S0012365X09001289
