Cook versus Karp-Levin: Separating completeness notions if NP is not small

Publisher： Elsevier

ISSN： 0304-3975

Source： Theoretical Computer Science, Vol.164, Iss.1, 1996-09, pp. : 141-163

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

Related content

Max NP-completeness made easy

By Crescenzi P. Trevisan L.

Theoretical Computer Science, Vol. 225, Iss. 1, 1999-08 ,pp. : 65-79

Elsevier

Access to resources Recommend Favorite

Cook's versus Valiant's hypothesis

By Burgisser P.

Theoretical Computer Science, Vol. 235, Iss. 1, 2000-03 ,pp. : 71-88

Elsevier

Access to resources Recommend Favorite

Strong NP-completeness of a matrix similarity problem

By Brimkov V. Codenotti B. Leoncini M. Resta G.

Theoretical Computer Science, Vol. 165, Iss. 2, 1996-10 ,pp. : 483-490

Elsevier

Access to resources Recommend Favorite

NP-completeness of the energy barrier problem without pseudoknots and temporary arcs

By Maňuch Ján

Natural Computing, Vol. 10, Iss. 1, 2011-03 ,pp. : 391-405

Springer Publishing Company

Access to resources Recommend Favorite

The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness

By Creignou N.

Theoretical Computer Science, Vol. 145, Iss. 1, 1995-07 ,pp. : 111-145

Elsevier

Access to resources Recommend Favorite