Minimum covering polyplet

A minimum covering polyplet (MCP) of a pattern is a polyplet (i.e. orthogonally/diagonally connected pattern) of minimal population covering said pattern.[1] The minimum covering polyplet size (MCPS) of a pattern is the size of a minimum covering polyplet[1]; unlike the minimum covering polyplet itself, this is a single, well-defined number.

Computation

Finding a minimum covering polyplet for a given pattern is an instance of the Steiner tree problem,[1] which is NP-hard; however, finding a minimum covering polyplet for a given small pattern is often easy in practice.

Uses

Oscar Cunningham proposed using the minimum covering polyplet size to gauge the size of a methuselah, as it penalizes both population and bounding box.[2] The resulting metric is L/MCPS.

gollark: ```As companies embrace buzzwords, a shortage of blockchain cryptocurrency connoisseurs opens. Only the finest theoretical code artisans with a background in machine learning (20 years of experience minimum) and artificial general intelligence (5+ years of experience) can shed light on the future of quantum computing as we know it. The rest of us simply can't hope to compete with the influx of Stanford graduates feeding all the big data to their insatiable models, tensor by tensor. "Nobody knows how these models really work, but they do and it's time to embrace them." said Boris Yue, 20, self-appointed "AI Expert" and "Code Samurai". But Yue wasn’t worried about so much potential competition. While the job outlook for those with computer skills is generally good, Yue is in an even more rarified category: he is studying artificial intelligence, working on technology that teaches machines to learn and think in ways that mimic human cognition. You know, just like when you read a list of 50000000 pictures + labels and you learn to categorize them through excruciating trial and error processes that sometimes end up in an electrified prod to the back and sometimes don't. Just like human cognition, and Yue is working on the vanguard of that.```
gollark: NO END!!!
gollark: No. END.
gollark: THERE IS NO END!
gollark: "finish"?

References
  1. Oscar Cunningham (January 20, 2018). Re: Largest and oldest methuselah ever found! (discussion thread) at the ConwayLife.com forums
  2. Oscar Cunningham (January 20, 2018). Re: Largest and oldest methuselah ever found! (discussion thread) at the ConwayLife.com forums
This article is issued from Conwaylife. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.