49 citations · 281 across the 55 of their papers we have counts for
20 papers · 1 filter
Unambiguous and Co-Nondeterministic Computations of Finite Automata and Pushdown Automata Families and the Effects of Multiple Counters
Tomoyuki Yamakami
Nonuniform families of polynomial-size finite automata and pushdown automata respectively have strong connections to nonuniform-NL and nonuniform-LOGCFL. We examine the behaviors o…
Complexity Classification of Complex-Weighted Counting Acyclic Constraint Satisfaction Problems
Tomoyuki Yamakami
We study the computational complexity of counting constraint satisfaction problems (#CSPs) whose constraints assign complex numbers to Boolean inputs when the corresponding constra…
Elementary Quantum Recursion Schemes That Capture Quantum Polylogarithmic Time Computability of Quantum Functions
Tomoyuki Yamakami
Quantum computing has been studied over the past four decades based on two computational models of quantum circuits and quantum Turing machines. To capture quantum polynomial-time…
Power of Counting by Nonuniform Families of Polynomial-Size Finite Automata
Tomoyuki Yamakami
Lately, there have been intensive studies on strengths and limitations of nonuniform families of promise decision problems solvable by various types of polynomial-size finite autom…
Parameterized-NL Completeness of Combinatorial Problems by Short Logarithmic-Space Reductions and Immediate Consequences of the Linear Space Hypothesis
Tomoyuki Yamakami
The concept of space-bounded computability has become significantly important in handling vast data sets on memory-limited computing devices. To replenish the existing short list o…
Supportive Oracles for Parameterized Polynomial-Time Sub-Linear-Space Computations in Relation to L, NL, and P
Tomoyuki Yamakami
We focus our attention onto polynomial-time sub-linear-space computation for decision problems, which are parameterized by size parameters , where the informal term "sub line…
State Complexity Characterizations of Parameterized Degree-Bounded Graph Connectivity, Sub-Linear Space Computation, and the Linear Space Hypothesis
Tomoyuki Yamakami
The linear space hypothesis is a practical working hypothesis, which originally states the insolvability of a restricted 2CNF Boolean formula satisfiability problem parameterized b…
A Schematic Definition of Quantum Polynomial Time Computability
Tomoyuki Yamakami
In the past four decades, the notion of quantum polynomial-time computability has been mathematically modeled by quantum Turing machines as well as quantum circuits. This paper see…
The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis
Tomoyuki Yamakami
We aim at investigating the solvability/insolvability of nondeterministic logarithmic-space (NL) decision, search, and optimization problems parameterized by natural size parameter…
Uniform-Circuit and Logarithmic-Space Approximations of Refined Combinatorial Optimization Problems
Tomoyuki Yamakami
A significant progress has been made in the past three decades over the study of combinatorial NP optimization problems and their associated optimization and approximate classes, s…
Counting list matrix partitions of graphs
Andreas Göbel, Leslie Ann Goldberg, Colin McQuillan +2
Given a symmetric D*D matrix M over {0,1,*}, a list M-partition of a graph G is a partition of G's vertices into D parts associated with the rows of M. The part of each vertex is c…
Constant Unary Constraints and Symmetric Real-Weighted Counting Constraint Satisfaction Problems
Tomoyuki Yamakami
A unary constraint (on the Boolean domain) is a function from {0,1} to the set of real numbers. A free use of auxiliary unary constraints given besides input instances has proven t…
Approximation Complexity of Complex-Weighted Degree-Two Counting Constraint Satisfaction Problems
Tomoyuki Yamakami
Constraint satisfaction problems have been studied in numerous fields with practical and theoretical interests. In recent years, major breakthroughs have been made in a study of co…
Optimization, Randomized Approximability, and Boolean Constraint Satisfaction Problems
Tomoyuki Yamakami
We give a unified treatment to optimization problems that can be expressed in the form of nonnegative-real-weighted Boolean constraint satisfaction problems. Creignou, Khanna, Suda…
A Dichotomy Theorem for the Approximate Counting of Complex-Weighted Bounded-Degree Boolean CSPs
Tomoyuki Yamakami
We determine the computational complexity of approximately counting the total weight of variable assignments for every complex-weighted Boolean constraint satisfaction problem (or…
Approximate Counting for Complex-Weighted Boolean Constraint Satisfaction Problems
Tomoyuki Yamakami
Constraint satisfaction problems (or CSPs) have been extensively studied in, for instance, artificial intelligence, database theory, graph theory, and statistical physics. From a p…
Immunity and Pseudorandomness of Context-Free Languages
Tomoyuki Yamakami
We discuss the computational complexity of context-free languages, concentrating on two well-known structural properties---immunity and pseudorandomness. An infinite language is RE…
Swapping Lemmas for Regular and Context-Free Languages
Tomoyuki Yamakami
In formal language theory, one of the most fundamental tools, known as pumping lemmas, is extremely useful for regular and context-free languages. However, there are natural proper…
Resource Bounded Immunity and Simplicity
Tomoyuki Yamakami, Toshio Suzuki
Revisiting the thirty years-old notions of resource-bounded immunity and simplicity, we investigate the structural characteristics of various immunity notions: strong immunity, alm…
Theory of One Tape Linear Time Turing Machines
Kohtaro Tadaki, Tomoyuki Yamakami, Jack C. H. Lin
A theory of one-tape (one-head) linear-time Turing machines is essentially different from its polynomial-time counterpart since these machines are closely related to finite state a…