Pac-Man Is NP-Hard

Main

Main/News Page
DCEmu Tutorials
DCEmu Console History
DCEmu Interviews

DCEmu Hosted Coder Releases
ZX81s Homebrew Releases
PSMonkeys Homebrew Releases
PLynxs Homebrew Releases
Miemt Homebrew Releases
Deniska Homebrew Releases
DXDev Releases
GPF Releases

Reviews
Console and Accessory Reviews Nintendo DS Reviews
Nintendo DS Review
Sony PSP Reviews
PSP Review
GP32 BLU Reviews
GP32 BLU Review
Dreamcast Reviews
Treamcast (2) Review
Treamcast Review
Hais Cooling Fan Review
Vcd player Review

GBA Reviews
GBA SP Movie Player (new Version) Review
GBA SP Movie Player Review
X-Rom Review
Afterburner Review
EZ Flash 2 Review
Memorystick Review
GBASP AV Adapter Review
GBASP Review
GBA Review
GBA Camera Review
EZ Flash Advance Review
Flash Linker Review
TV Tuner Review
XG Flash Review
PS2 Reviews
Maxevo Review
Premodded PS2 Review
Slidetool Review
DMS 3 Review
Magic3 Review
Magic2 Review
Apple Review
Messiab Review
Swap Disc Review

Xbox Reviews
SmartXX LT OPX review
Xecuter 3 CE review
SmartXXv2review
X-Tender Xbox Case review
Xapter Review
Xenium ICE Review
Xenium Solderless Adapter Review
SmartXX Review
Xenium Review
Joytech tft Monitor Review
X-B.I.T Review
X2.2 Pro Review
X2.2 Lite Review
Chameleon Review
Matrix Review
Enigmah Review
Executor Review
CheapMod Review
X-Elixis Review
X-ecutor 2 Lite Review
Xbox Modchips
Xbit Information

Social Media

Facebook

DCEmu Theme Park News
Wraggys Beers Wines and Spirits

Youtube

Wraggys Beers Wines and Spirits
DCEmu Theme Park News Videos
Gamer Wraggy 210

Twitter

Wraggys Twitter

News Archive

January 27th, 2012, 01:10 Posted By: wraggster

An Italian researcher with a penchant for retro games — or perhaps just looking for an excuse to play games in the name of science! — has used computational complexity theory to decide, once and for all, just how hard video games are. In a truly epic undertaking, Giovanni Viglietta of the University of Pisa has worked out the theoretical difficulty of 13 old games, including Pac-Man, Doom, Lemmings, Prince of Persia, and Boulder Dash. Pac-Man, with its traversal of space, is NP-hard. Doom, on the other hand, is PSPACE-hard.

http://games.slashdot.org/story/12/0...man-is-np-hard

For more information and downloads, click here!

There are 0 comments - Join In and Discuss Here

Forum Info

Users online:

Guests online: 12587. Total online: 12587.

You have to register or login before you can post on our forums or use our advanced features.

Total threads: 206,257
Total posts: 750,048

Go to the forum

Buy Retro Consoles

Advert

Latest Retro Homebrew and Console News

Respawn and Oculus documentary wins an Oscar
Arcades are a crucial part of the history of video games
GoldenEye, Mario and how to succeed in the world of nostalgia
Classic99 v399.37
ColEm v5.5
VirtualC64 v4.0b4
Kernal64 v1.7.0b15
WinUAE v4.5.0 Beta 16
Tsugaru (2021/01/14)
HITACHI MB-S1 v0.5.3
MARK5 Emulator v1.7.3
Emma 02 v1.38
EightyOne v1.20
Stella v6.5.1
Gopher2600 v0.8.1
Steem SSE v4.0.2 R30
New Utilities Added
New Translations Added
New Hacks Added
New Homebrew Added
Stella v6.5
DSP Emulator v0.18b3 (2021/01/10)
Caprice Forever v21.1
CPCEMU v2.0
BeebEm v4.16
Tsugaru (2020/12/29)
WinUAE v4.5.0 Beta 15
Joyce v2.2.14
WinArcadia & AmiArcadia v26.83
CPCEC / ZXSEC (2021/01/05) - Amstrad CPC models 464, 664 and 6128 Emulator for Window
VICE v3.5
ZX-Poly v2.1.2
EmuZ-2000 TF-Edition Ver.0.95.6
Speccy v5.6
Altirra v4.00 Test 24
Hatari v2.3.1
Steem SSE v4.0.2 R27
Z64k (2020/12/30)
DSP Emulator v0.18b3 (2020/12/30)
Christmas with Wizardry 1 WonderSwan Color port now fully playable in English!
Super-Go-Down-The-Hole - Amiga
Axel Tetris - Amiga
Ninja Carnage - Amstrad!
Krpat - ZX Spectrum
Streets of Rage Amiga
Wonder Boy Remake - Amstrad 128k
Zap Fight Trilogy - C64
KFC Gaming officially announces the KFConsole
ROGER THE PANGOLIN - A new speccy game
Suite Macabre - released for the MSX
WinUAE v4.5.0 Beta 13
Neuromancer DOS - A classic game, a classic Cyberpunk review
This UNREAL ENGINE 4 Remake of the Commodore 64 'Uridium'
Outrage - After 30 years a fabulous C64 'Hawkeye' style game
mini MIKE and the Caverns of Doom - A challenging C64 demo
Tiny Quest - Ultimate Bundle Limited Edition – Tape and Disk Pre-Orders for the C64
Manic Panic - A ZX Spectrum
Alcon 2020 (Slap Fight) - Amstrad
L'abbaye Des Morts - A high quality Falcon
Oyup! C64
Monster Catcher -C64
Chiller 2 - C64 game
Deepstone Catacomb - Atari 2600!
Savage Princess - A new ZX Spectrum game
An Indie Retro News special event! - C64 Game Awards 2020
Alcon 2020 (Slap Fight) - Amstrad
Wonderful Dizzy - Dizzy ZX Spectrum
Black Dawn Rebirth -for the Amiga
A Very Sheepy Xmas - A Christmas themed game for the ZX Spectrum
Nox Archaist - Multi-System RPG
Santa Factory (Atari Lynx Game)
Yape v1.1.8
Classic99 v399.33
Cpcec / zxsec (2020/12/12)
DSP Emulator v0.18b3 (2020/12/14)
fMSX v5.9
WinArcadia & AmiArcadia v26.82
The $400 dungeon crawler: Madou Monogatari I: Honoo no Sotsuenji translation released
Wonderful Dizzy - A new Dizzy ZX adventure
UNREAL ENGINE 4 Remake of the Commodore 64 'Uridium'
Wonderful Dizzy - ZX Spectrum
Parallaxian - C64/C128 game
Dread - Doom clone on the Amiga 500
Putter - Amiga demo
Steem SSE v4.0.2 R24
The latest Raycaster Engine for the TI 99/4a
Scourge of the Underkind (Amiga)
EmuTos v1.0.1
Altirra v4.00 Test 23
Caprice Forever v20.12
Zombie Island - A work in progress or concept action platformer for the C64
The latest Raycaster Engine for the TI 99/4a looks superb!
A-PI 400 - A printed Amiga case for the Raspberry Pi 400?
This incredible demake of 'DOOM' as POOM on the Pico-8 is mind blowing!
EightyOne v1.19
Agat Emulator v1.29.2
Xpeccy 0.6.20201202
C64 Xmas Bundle - A bundle of C64 games for Xmas and beyond!
Mini Multiplayer RPG has been announced for the C64
Meonlawel - A beautiful C64/128 RPG is in development
Blastr - Atari XL/XE shooter
Protopad - Crowd funding campaign for a new C64 game pad (Atari/Amiga Compatible)
Gopher2600 v0.7.2
DSP Emulator v0.18b3 (2020/12/01)
Updated Translations
Updated Hacks Added
Yoyo's Great Adventure - ZX Spectrum game
Outrage C64!
PockEmul v2.1.0
Emu48+ v1.62
Free42 v2.5.22
River Raid Cold Winter - Atari XL/XE
CODE-112 - ZX Spectrum
Bullet Storm - Tactical ZX Spectrum shoot em up
ZEsarUX v9.1
Hatari v2.3.0
Astro Blox Revisited - Amiga game
Super Metal Hero - Amiga
Red Raid - ZX Spectrum release
Marsmare: Alienation - Arcade ZX Spectrum
White Jaguar - ZX Spectrum
Crown prince of Saudi Arabia's foundation to buy 51% stake in SNK
An Amiga games pack released
Cpcec / zxsec (2020/11/22)
Tristam Island - A command text based adventure with over 30 classic system support!
Dizzy V - Spellbound Dizzy - Commodore Plus/4 conversion
Heart of Darkness on the Amiga
DSP Emulator v0.18b3 (2020/11/23)
WinUAE v4.5.0 Beta 11
Xpeccy 0.6.20201122
Emma 02 v1.37
SugarBox v1.99.2
Mutation Gold Compilation and CyberPunks 2 Amiga announcement
Wolfling Teaser - Nesdev game teased on the C64
Looty V2 - Amiga game
Metamorphosis - An in-dev ZX Spectrum game
Mire Mare - ZX Spectrum homebrew
Altirra v4.00 Test 20
Denise v1.0.9.1
Tsugaru (2020/11/11)
Cpcec / zxsec (2020/11/11)
The Abduction of Oscar Z - Amstrad CPC
Adam is Me - Atari XL/XE
Super Pumpkin Bros - Amiga game
LiteRally for the Atari XL/XE
Juanje Juega in Sinverland released for the C64
Devwill Too ZX - An Arcade platformer released for the ZX Spectrum
CPCRetroDev 2020 results
Twenty Four Hour Parsley People released for the ZX Spectrum!
New Utilities Added to the Database
New Translations Added to the Database
New Hacks Added to the Database
Updated Hacks Added to the Database
Caprice Forever v20.10
ColEm v5.4
WinArcadia & AmiArcadia v26.81
Cpcec / zxsec (2020/10/22)
Denise v1.0.9
Speccy v5.5
Stella v6.4
AppleWin v1.29.16.0
Tsugaru (2020/11/04)
ZEsarUX v9.1 Beta 1
WinUAE v4.5.0 Beta 10
Dapplegrey v7.6.5
Classic99 v399.32
Altirra v4.00 Test 19
New Translations Added
New Hacks Added
Crash n the Boys Take to the Soccer Field
New Translations Added
New Hacks Added
New Homebrew Added
New Translations Added
New Hacks Added
Hey Digimon! English Translation of Tag Tamers is now available
New Translations Added
New Hacks Added
Intellivision Amico delayed to April 2021
Montezuma's Redux - 1980's Atari 8-bit
Altirra v3.90
A7800 v4.0
Hoxs64 v1.1.0.4
Stella v6.2.1
Classic99 v399.28
WinArcadia & AmiArcadia v26.5
WinUAE v4.4.0 Beta 8
ColEm v5.1
EON AMIGA AGA - Shadow of the Beast inspiration
The Sword of Ianna
ZetaWing - Another Shoot em up incoming for the C64
BlitzWays - A brand new Amiga 500 game
DOS Mario Ported to Commodore Amiga as Amigo, Work in Progress
Super Mario Bros Texas Instruments 99/4A Preview 4 Released
Alien 8 - Ultimate Play the Game classic
Cocoa and the Time Machine
Zambeezi - Previously unknown Mr Chip game
Rat A Tat - Another NEW ZX Spectrum 128k game
Atic Atac - Ultimate Play the Game classic
Legacy of the Beast

The DCEmu Homebrew and Gaming Network

Welcome to the DCEmu Homebrew and Gaming Network. This Network of sites is owned and ran by fans of all games consoles, we post news on all the consoles we cover about hardware aspects, gaming and Homebrew. Homebrew and Emulation are software thats made using free and legal tools to play on games consoles. This Network is the only worldwide network of sites where coders can upload and post comments they deserve for all their hardwork. We have a Network that currently supports PSVita, WiiU, Nintendo Wii, Xbox360, PS3, PS2,PS1, Snes, N64, Gameboy, Nes, Xbox, Gamecube, Nintendo DS, PSP, GBA, Dreamcast, Sega Saturn,3DS, DSi, Switch, PS4, Pandora, xboxone, GP2X, iPhone, Windows Phone, iPad, Android and also Mobile Phone Emulation. When new consoles appear we will expand to cover those consoles. We also cover Theme Park News and news and reviews of Beer, cider, lager, wines and spirits. news of their own releases and get the credit and Please help DCEmu become stronger by posting on the forums every day and make our community larger.