Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Mitsunori Ogihara:

TR05-011 | 21st December 2004
Christian Gla├čer, Mitsunori Ogihara, A. Pavan, Alan L. Selman, Liyu Zhang

Autoreducibility, Mitoticity, and Immunity

We show the following results regarding complete sets:

NP-complete sets and PSPACE-complete sets are many-one

Complete sets of any level of PH, MODPH, or
the Boolean hierarchy over NP are many-one autoreducible.

EXP-complete sets are many-one mitotic.

NEXP-complete sets are weakly many-one mitotic.

PSPACE-complete sets are weakly Turing-mitotic.

... more >>>

TR02-016 | 30th January 2002
Alina Beygelzimer, Mitsunori Ogihara

On the Enumerability of the Determinant and the Rank

We investigate the complexity of enumerative approximation of
two elementary problems in linear algebra, computing the rank
and the determinant of a matrix. In particular, we show that
if there exists an enumerator that, given a matrix, outputs a
list of constantly many numbers, one of which is guaranteed to
more >>>

TR01-061 | 13th July 2001
Mitsunori Ogihara, Seinosuke Toda

The Complexity of Computing the Number of Self-Avoiding Walks in Two-Dimensional Grid Graphs and in Hypercube Graphs

Revisions: 2

Valiant (SIAM Journal on Computing 8, pages 410--421) showed that the
roblem of counting the number of s-t paths in graphs (both in the case
of directed graphs and in the case of undirected graphs) is complete
for #P under polynomial-time one-Turing reductions (namely, some
post-computation is needed to ... more >>>

TR96-027 | 20th February 1996
Lane A. Hemaspaandra, Ashish Naik, Mitsunori Ogihara, Alan L. Selman

Computing Solutions Uniquely Collapses the Polynomial Hierarchy

Is there an NP function that, when given a satisfiable formula
as input, outputs one satisfying assignment uniquely? That is, can a
nondeterministic function cull just one satisfying assignment from a
possibly exponentially large collection of assignments? We show that if
there is such a nondeterministic function, then the polynomial ... more >>>

TR96-024 | 21st March 1996
Eric Allender, Robert Beals, Mitsunori Ogihara

The complexity of matrix rank and feasible systems of linear equations

We characterize the complexity of some natural and important
problems in linear algebra. In particular, we identify natural
complexity classes for which the problems of (a) determining if a
system of linear equations is feasible and (b) computing the rank of
an integer matrix, ... more >>>

TR96-014 | 14th February 1996
Mitsunori Ogihara

Sparse Hard Sets for P Yields Space-Efficient Algorithms

In 1978, Hartmanis conjectured that there exist no sparse complete sets
for P under logspace many-one reductions. In this paper, in support of
the conjecture, it is shown that if P has sparse hard sets under logspace
many-one reductions, then P is included in DPSPACE[log^2 n].

more >>>

TR96-013 | 14th February 1996
Mitsunori Ogihara

The PL Hierarchy Collapses

It is shown that the PL hierarchy defined in terms of the
standard Ruzzo-Simon-Tompa relativization collapses to PL.

more >>>

ISSN 1433-8092 | Imprint