Zobrazeno 1 - 3
of 3
pro vyhledávání: '"Mihir Singhal"'
Autor:
Adam Hesterberg, Michael J. Coulombe, Erik D. Demaine, Mihir Singhal, Jayson Lynch, Sualeh Asif, Martin L. Demaine
Publikováno v:
Journal of Information Processing. 28:942-958
We prove that the classic falling-block video game Tetris (both survival and board clearing) remains NP-complete even when restricted to 8 columns, or to 4 rows, settling open problems posed over 15 years ago [BDH+04]. Our reduction is from 3-Partiti
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::1c4412e4dae7dde8328c9c59c6088779
https://doi.org/10.2197/ipsjjip.28.942
https://doi.org/10.2197/ipsjjip.28.942
Autor:
Mihir Singhal
We consider families of $k$-subsets of $\{1, \dots, n\}$, where $n$ is a multiple of $k$, which have no perfect matching. An equivalent condition for a family $\mathcal{F}$ to have no perfect matching is for there to be a blocking set, which is a set
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5acd278a010b76fed84dc9d666131a7a
http://arxiv.org/abs/2008.08792
http://arxiv.org/abs/2008.08792
A permutation $\sigma\in S_n$ is said to be $k$-universal or a $k$-superpattern if for every $\pi\in S_k$, there is a subsequence of $\sigma$ that is order-isomorphic to $\pi$. A simple counting argument shows that $\sigma$ can be a $k$-superpattern
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0ed7db5c198d31280204c0d9c31677d4
http://arxiv.org/abs/2004.02375
http://arxiv.org/abs/2004.02375