Tuesday, November 30, 2010

Time Complexity

An algorithm is PN-Complete if it can be transformed in polynomial-time to the 3-SAT problem.

Actually, it is PN-Complete if it can be transformed to an NP-Complete problem in polynomial time.

Reference: Computers and Intractability by M. R. Garey, D. S. Johnson. W. H. Freeman, 1979.

No comments:

Post a Comment