Author name cluster

Shigeki Iwata

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

2 author rows

TCS Journal 2004 Journal Article

Some minimum merging networks

Gembu Morohashi
Shigeki Iwata

Let M ( m, n ) be the minimum number of comparators which constructs an ( m, n ) -merging network. Batcher's odd–even merge, which is a merging network constructed by his algorithm, provides the best upper bound for M ( m, n ) to date. Recently Iwata (Inform. and Comput. 168 (2001) 187) analyzed the property of leftmost comparators, and showed M ( m 1 + m 2, n ) ⩾ ⌈ ( M ( m 1, n ) + M ( m 2, n ) + m 1 + m 2 + n - 2 ) / 2 ⌉. We extend Iwata's proofs and show that Batcher's ( 6, 8 k + 7 ) -, ( 9, 16 k + 9 ) -, ( 7, 8 ) -merging networks are optimal for all k ⩾ 0. In Batcher's ( m, n ) -merging network, the ith smallest element out of m elements and another ith smallest element out of n elements are first compared for all i ( 1 ⩽ i ⩽ min { m, n } ). Under an assumption of existence of such min { m, n } comparators in optimal ( m, n ) -merging networks, we show that M ( n, n ) = M ( n - 1, n ) + 1 = M ( n - 2, n ) + 3.

Details DOI

I&C Journal 2001 Journal Article

Lower Bounds for Merging Networks

Shigeki Iwata

A lower bound theorem is established for the number of comparators in a merging network. Let M(m, n) be the least number of comparators required in the (m, n)-merging networks, and let C(m, n) be the number of comparators in Batcher's (m, n)-merging network, respectively. We prove for n≥1 that M(4, n)=C(4, n) for n≡0, 1, 3 mod 4, M(4, n)≥C(4, n)−1 for n≡2 mod 4, and M(5, n)=C(5, n) for n≡0, 1, 5 mod 8. Furthermore Batcher's (6, 8k+6)-, (7, 8k+7)-, and (8, 8k+8)-merging networks are optimal for k≥0. Our lower bound for (m, n)-merging networks, m≤n, has the same terms as C(m, n) has as far as n is concerned. Thus Batcher's (m, n)-merging network is optimal up to a constant number of comparators, where the constant depends only on m. An open problem posed by Yao and Yao (Lower bounds on merging networks, J. Assoc. Comput. Mach. 23, 566–571) is solved: lim n→∞ M(m, n)/n=⌈log m⌉/2+m/2⌈log m⌉.

Details DOI

TCS Journal 1994 Journal Article

The Othello game on an n × n board is PSPACE-complete

Shigeki Iwata
Takumi Kasai

Given an arbitrary position of the Othello game played on an n × n board, the problem of determining the winner is shown to be PSPACE-complete. It can be reduced from generalized geography played on bipartite graphs with maximum degree 3.

Details DOI

TCS Journal 1987 Journal Article

Simultaneous (poly-time, log-space) lower bounds

Shigeki Iwata
Takumi Kasai

In this paper we establish a lower bound for the simultaneous complexity of the halting problem for a class of ‘simple programs’, which allow setting variables to constants and if-goto statements. Let HALT(h, k) be the problem: given a simple program P k with k variables, determine whether P k halts within n h steps, where n is the length of P k. We show that the problem HALT(h, k) cannot be solved in time less than n (h−4) 2 and space less than 1 4 (k − 17) log 2 n by any Turing machine with one storage tape and binary storage symbols.

Details DOI

STOC Conference 1981 Conference Paper

Low Level Complexity for Combinatorial Games

Akeo Adachi
Shigeki Iwata
Takumi Kasai

There have been numerous attempts to discuss the time complexity of problems and classify them into hierarchical classes such as P, NP, PSPACE, EXP, etc. A great number of familiar problems have been reported which are complete in NP (nondeterministic polynomial time). Even and Tarjan considered generalized Hex and showed that the problem to determine who wins the game if each player plays perfectly is complete in polynomial space. Shaefer derived some two-person game from NP complete problems which are complete in polynomial space.

Details