Shigeki Iwata

Available identifiers

Publication	Date of Publication	Type
Shikaku and Ripple Effect are NP-complete	2014-04-02	Paper
Posets with seven linear extensions sortable by three comparisons	2013-03-28	Paper
NP-completeness of two pencil puzzles: Yajilin and Country Road	2012-12-29	Paper
Some minimum merging networks	2005-02-09	Paper
Lower bounds for merging networks	2003-01-14	Paper
https://portal.mardi4nfdi.de/entity/Q4703658	1999-12-15	Paper
The Othello game on an \(n\times n\) board is PSPACE-complete	1994-02-22	Paper
Relations among simultaneous complexity classes of nondeterministic and alternating Turing machines	1993-01-01	Paper
https://portal.mardi4nfdi.de/entity/Q4206403	1990-01-01	Paper
Simultaneous (poly-time, log-space) lower bounds	1987-01-01	Paper
https://portal.mardi4nfdi.de/entity/Q3785950	1987-01-01	Paper
A note on some simultaneous relations among time, space, and reversal for single work tape nondeterministic turing machines	1986-01-01	Paper
https://portal.mardi4nfdi.de/entity/Q3802609	1986-01-01	Paper
Gradually intractable problems and nondeterministic log-space lower bounds	1985-01-01	Paper
Some combinatorial game problems require Ω( n ^k ) time	1984-01-01	Paper
https://portal.mardi4nfdi.de/entity/Q3217602	1984-01-01	Paper
https://portal.mardi4nfdi.de/entity/Q3895389	1980-01-01	Paper
Classes of Pebble Games and Complete Problems	1979-01-01	Paper
Programs with minimal goto statements	1978-01-01	Paper

This page was built for person: Shigeki Iwata