Shigeki Iwata

List of research outcomes

This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!

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 Information Processing Letters	2013-03-28	Paper
NP-completeness of two pencil puzzles: Yajilin and Country Road	2012-12-29	Paper
Some minimum merging networks Theoretical Computer Science	2005-02-09	Paper
Lower bounds for merging networks Information and Computation	2003-01-14	Paper
scientific article; zbMATH DE number 1379309 (Why is no real title available?)	1999-12-15	Paper
The Othello game on an \(n\times n\) board is PSPACE-complete Theoretical Computer Science	1994-02-22	Paper
Relations among simultaneous complexity classes of nondeterministic and alternating Turing machines Acta Informatica	1993-01-01	Paper
scientific article; zbMATH DE number 4126702 (Why is no real title available?)	1990-01-01	Paper
Simultaneous (poly-time, log-space) lower bounds Theoretical Computer Science	1987-01-01	Paper
scientific article; zbMATH DE number 4049059 (Why is no real title available?)	1987-01-01	Paper
A note on some simultaneous relations among time, space, and reversal for single work tape nondeterministic turing machines Information and Control	1986-01-01	Paper
scientific article; zbMATH DE number 4070311 (Why is no real title available?)	1986-01-01	Paper
Gradually intractable problems and nondeterministic log-space lower bounds Mathematical Systems Theory	1985-01-01	Paper
Some combinatorial game problems require Ω( n ^k ) time Journal of the ACM	1984-01-01	Paper
scientific article; zbMATH DE number 3883610 (Why is no real title available?)	1984-01-01	Paper
scientific article; zbMATH DE number 3702547 (Why is no real title available?)	1980-01-01	Paper
Classes of Pebble Games and Complete Problems SIAM Journal on Computing	1979-01-01	Paper
Programs with minimal goto statements Information and Control	1978-01-01	Paper

Research outcomes over time

This page was built for person: Shigeki Iwata