Primes and Squares

« first day (158 days earlier) ← previous day next day → last day (1066 days later) »

orlp

02:34

this is a really nice introduction to generating functions: ocw.mit.edu/courses/electrical-engineering-and-computer-science/…

Nathan Merrill

02:58

if any of you are interested in some puzzle games, and don't mind poor graphics, I really recommend checking out DROD and Quadrax. (I recently found them on an old HD of mine, and I'm remembering how tough these puzzles were)

10 hours later…

flawr

12:28

@orlp a more comprehensive book: math.upenn.edu/~wilf/gfologyLinked2.pdf

El'endia Starman

13:19

Are there "degrees" of isomorphisms? Like, if you have two graphs that are isomorphic except for one edge, they're "more isomorphic" than two graphs that differ by two edges.

Martin Ender

@El'endiaStarman mathoverflow.net/q/163958/56581 ?

El'endia Starman

@MartinEnder Sounds like it.

Martin Ender

(googled for "distance measure between graphs", which also brings up en.wikipedia.org/wiki/Graph_edit_distance)

El'endia Starman

@MartinEnder Oh, this looks more like what I was thinking of.

Nathan Merrill

13:42

@MartinEnder Despite the above algorithms sometimes working well in practice, in general the problem of computing graph edit distance is NP-complete[15] (for a proof that's available online, see Section 2 of Zeng et al.), and is even hard to approximate (formally, it is APX-hard[16]).

that's crazy hard

Martin Ender

unsurprisingly, though

Nathan Merrill

oh yeah, I was saying to myself: "This has got to be a hard problem" as I was opening the page

that said, your intuition in how difficult a problem is can be drastically wrong.

like the Knapsack problem. It seems really easy when you first hear about it

Martin Ender

@NathanMerrill from the wikipedia description, DROD reminds me a bit of Trap Them store.steampowered.com/app/375930/Trap_Them

(which isn't entirely turn-based though)

if you're into tough DOS-era puzzle games though I can highly recommend Pushover

Nathan Merrill

I'm into tough puzzle games. I don't care the era :)

Martin Ender

Sp3000 recommended Stephen's Sausage Roll as a super tough puzzle game (and it's currently on sale)

Nathan Merrill

13:53

that video on steam is super useless

all it does is show the "sausage roller" (if that's what that is) in different levels

no movement or anything

Martin Ender

I think that's on purpose

as is the useless game description

orlp

@NathanMerrill knapsack is easy for real world problems

it has complexity O(nW) where W is the maximum weight

the reason it's still called NP-complete is because W is not a parameter of the length of the input

flawr

@NathanMerrill I think even determining if two graphs are isomorphic is very hard.

Martin Ender

> The problem is not known to be solvable in polynomial time nor to be NP-complete, and therefore may be in the computational complexity class NP-intermediate.
> It is known that the graph isomorphism problem is in the low hierarchy of class NP, which implies that it is not NP-complete unless the polynomial time hierarchy collapses to its second level.[1] At the same time, isomorphism for many special classes of graphs can be solved in polynomial time, and in practice graph isomorphism can often be solved efficiently.

Nathan Merrill

@MartinEnder First review: "The game demands both creativity and intellect in great amounts. But even more importantly, the game demonstrates a uniqueness highly uncommon today, it isn't derivative in the least. " TrapThem" may be the greatest puzzle-sensation since "DROD" "

you clearly aren't alone

Martin Ender

13:58

haha

Martin Ender

14:38

@NathanMerrill have you played Sokobond?

El'endia Starman

Off-topic, but this is the company I work for: wbgamesny.com

Martin Ender

15:07

well, we were talking about games :P