Mutilated chessboard problem is exponentially hard for resolution

Author： Alekhnovich M.  

Publisher： Elsevier

ISSN： 0304-3975

Source： Theoretical Computer Science, Vol.310, Iss.1, 2004-01, pp. : 513-525

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

MAX3SAT is exponentially hard to approximate if NP has positive dimension

By M. Hitchcock J.  

Theoretical Computer Science, Vol. 289, Iss. 1, 2002-10 ,pp. : 861-869

Elsevier

Access to resources Recommend Favorite

Resolution of Hartmanis' conjecture for NL-hard sparse sets

By Cai  

Theoretical Computer Science, Vol. 240, Iss. 2, 2000-06 ,pp. : 257-269

Elsevier

Access to resources Recommend Favorite

A Hard Dial-a-Ride Problem that is Easy on Average

By Coja-Oghlan Amin   Krumke Sven   Nierhoff Till  

Journal of Scheduling, Vol. 8, Iss. 3, 2005-06 ,pp. : 197-210

Springer Publishing Company

Access to resources Recommend Favorite

A hard clustering approach to the part family formation problem

By Al-Sultan K. S.  

Production Planning and Control, Vol. 8, Iss. 3, 1997-04 ,pp. : 231-236

Taylor & Francis Ltd

Access to resources Recommend Favorite

The word problem for 1LC congruences is NP-hard

By Rosaz L.  

Theoretical Computer Science, Vol. 306, Iss. 1, 2003-09 ,pp. : 245-268

Elsevier

Access to resources Recommend Favorite