All › Computer science › Polynomial versus nondeterministic-polynomial time for specific algorithmic problems

More in “Polynomial versus nondeterministic-polynomial time for specific algorithmic problems”

• Can integer factorization be done in polynomial time on a classical (non-quantum) computer?
• Can the discrete logarithm be computed in polynomial time on a classical (non-quantum) computer?
• Can the graph isomorphism problem be solved in polynomial time on a classical computer?
• Is graph canonization polynomial-time equivalent to the graph isomorphism problem?
• Can leaf powers and k-leaf powers be recognized in polynomial time?
• Can parity games be solved in polynomial time?
• Can graphs of bounded clique-width be recognized in polynomial time?
• Can one find a simple closed quasigeodesic on a convex polyhedron in polynomial time?

Another random computer science problem →