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.
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.
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.
Subscribe to:
Post Comments (Atom)
Posts
No comments:
Post a Comment