Forgot your password?

typodupeerror

Comment: It *is* possible to build a reactionless drive... (Score 4, Informative) 419

by Bob Hearn (#42829217) Attached to: China's Radical New Space Drive

... sort of. And it is established physics. See Swimming in Spacetime: Motion by Cyclic Changes in Body Shape, Science, 2/27/2003, by Jack Wisdom.

But this mechanism relies on general relativistic effects, and only works in curved spacetime. Momentum conservation is not violated, because while the location of the object changes, its momentum (thus velocity) does not -- it simply cyclicly translates itself through space.

My first thought reading about the EmDrive was that Shaywer had found a way to reproduce this effect using a microwave cavity. But unless I'm mistaken, this does not appear to be the case, and I don't follow the arguments that Shaywer's drive should work.

Comment: Re:I don't get why... (Score 1) 322

by Bob Hearn (#31791714) Attached to: All the Best Games May Be NP-Hard

The reason that fun games tend to be NP-hard (or harder) is that if a game's "physics" supports interesting constructions requiring complex reasoning to solve, then probably that same physics can be used to build computational gadgets, which is how you show hardness of the generalized version. This quality expresses itself even on small, fixed-size board.

Comment: Re:Just to throw this out there (Score 2, Interesting) 322

by Bob Hearn (#31791376) Attached to: All the Best Games May Be NP-Hard

Ah, it doesn't mean that either. :-)

If a problem is NP-hard, it means it is at least as hard as any other problem that can be solved in polynomial time on a nondeterministic computer.

It is an open question (P=NP) whether this is equivalent to saying that there is no deterministic polynomial-time algorithm.

Comment: Re:chess and go aren't np-hard, but they are also (Score 5, Informative) 322

by Bob Hearn (#31791308) Attached to: All the Best Games May Be NP-Hard

Chess and Go are actually EXPTIME-complete, even harder than NP-complete problems and PSPACE-complete problems.

In general, one-player games of bounded length (like Flood-It, or Sudoku) tend to be NP-complete; one-player unbounded games (like sliding-block puzzles, or Sokoban) tend to be PSPACE-complete; two-player bounded-length games (like Hex, or Amazons) also tend to be PSPACE-complete, and two-player unbounded games (like Chess, Checkers, and Go) tend to be EXPTIME-complete.

I can't resist here a plug for my book (with Erik Demaine), Games, Puzzles, and Computation, which discusses all these issues in detail. A theme running throughout the book is the same as the view expressed in this paper: most interesting games and puzzles seem to be as hard as their "natural" complexity class, outlined above.

"The one charm of marriage is that it makes a life of deception a neccessity." - Oscar Wilde

Working...