4. Find the academic paper by Erik Demaine (and others) that talks about Tetris

Question

4. Find the academic paper by Erik Demaine (and others) that talks about Tetris and NP-Completeness

and answer the following questions:

(a) What problem are they proving is NP-Complete? (Tetris" isn't a complete answer to this

question. I am not asking you to copy the detailed description of how the authors made a decision

problem from the game Tetris. Instead, I want a simple explanation of what yes/no question they

are asking in their Tetris decision problem.)

(b) What NP-Complete problem did they reduce to their problem? Give a small example instance of that problem.

(c) How old was Erik Demaine when that paper was presented at COCOON (an academic conference)?

Explanation / Answer

(a)
NP is set of decision problems which can be solved by a Non-deterministic

Turing Machine in Polynomial time.

NP complete problems are problems whose status is unknown.

(b)

Every problem in NP is reducible to L in polynomial time.

L is in NP any given solution for NP-complete problems can be verified quickly.

(C)

at the age of 17 erik demaine was presented at cocoon.

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.