Revision #2 Authors: Maciej Liskiewicz, Mitsunori Ogihara, Seinosuke Toda

Accepted on: 16th October 2001 00:00

Downloads: 2876

Keywords:

Valiant (SIAM Journal on Computing 8, pages 410--421) showed that the

problem of computing the number of simple s-t paths in graphs is

#P-complete both in the case of directed graphs and in the case of

undirected graphs. Valiant then asked whether the self-avoiding walk

problem on the two-dimensional grid, the problem of computing the

number of self-avoiding walks of a given length in the two-dimensional

grid is complete for #P_1, the tally-version of #P. This paper offers

a partial answer to the question of Valiant. It is shown that computing

the number of self-avoiding walks of a given length in the

two-dimensional grid graph is #P-complete. The paper also studies

several variations of the prolem and shows that all of them are

#P-complete.

This paper also studies the problem of computing the number of

self-avoiding walks in graphs embedded in a hypercube. Similar

completeness results are shown for hypercube graphs. By scaling the

computation time to exponential, it is shown that computing the number

fo self-avoiding walks in the hypercubes is complete for #EXP in the

case when a hypercube graph is specified by its dimension and

a boolean circuit that accepts the nodes.

Finally, this paper studies the complexity of testing whether a given

word over the four letter alphabet { U, D, L, R } is a self-avoiding

walk. A linear-space lower bound is shown for nondeterministic Turing

machines with a one-way input head to recognize self-avoiding walks.

Revision #1 Authors: Maciej Liskiewicz, Mitsunori Ogihara, Seinosuke Toda

Accepted on: 10th October 2001 00:00

Downloads: 2253

Keywords:

Valiant (SIAM Journal on Computing 8, pages 410--421) showed

that the problem 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 recover the value of a #P-function).

Valiant then asked whether the problem of counting the number of

self-avoiding walks of length n in the two-dimensional grid is complete

for #P_1, i.e., the tally-version of #P. This paper offers a partial

answer to the question. It is shown that a number of versions of the

problem of computing the number of self-avoiding walks in

two-dimensional grid graphs (graphs embedded in the two-dimensional

grid) is polynomial-time one-Turing complete for #P.

This paper also studies the problem of counting the number of

self-avoiding walks in graphs embedded in a hypercube. It is shown

that a number of versions of the problem is polynomial-time

one-Turing complete for #P, where a hypercube graph is

specified by its dimension, a list of its nodes, and a list of its

edges. By scaling up the completeness result for #P, it is

shown that the same variety of problems is polynomial-time one-Turing

complete for #EXP, where the post-computation required is right

bit-shift by exponentially many bits and a hypercube graph is specified

by: its dimension, a boolean circuit that accept its nodes, and oneu

that accepts its edges.

Finally, this paper studies the complexity of testing whether a given

word over the four letter alphabet { U, L, D, R } is a self-avoiding

walk. It shows a linear-space lower bound for nondeterminstic Turing

machines with a one-way input head.

TR01-061 Authors: Mitsunori Ogihara, Seinosuke Toda

Publication: 3rd September 2001 16:33

Downloads: 2502

Keywords:

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 recover the value of a #P-function).

Valiant then asked whether the problem of counting the number of

self-avoiding walks of length n in the two-dimensional grid is complete

for #P1, i.e., the tally-version of #P. This paper offers a partial

answer to the question. It is shown that a number of versions of the

problem of computing the number of self-avoiding walks in

two-dimensional grid graphs (graphs embedded in the two-dimensional

grid) is polynomial-time one-Turing complete for #P.