answersLogoWhite

0


Best Answer

You can use the bounded tiling problem. Given a problem in NP A, it has a turing machine M that recognizes its language. We construct tiles for the bounded tiling problem that will simulate a run of M.

Given input x, we ask if there is a tiling of the plane and answer that will simulate a run of M on x. We answer true iff there is such a tiling.

User Avatar

Wiki User

14y ago
This answer is:
User Avatar

Add your answer:

Earn +20 pts
Q: What is the first np-hard problem?
Write your answer...
Submit
Still have questions?
magnify glass
imp