• Consider the complexity of edge-coloring on a complete graph. • Prove the PPP - and PWPP - completeness of the problems based on the Ward and Szabó theorem. • Introduce some new variants of Pigeon , a PPP -complete problem. • Show the computational aspects of our new variant of Pigeon . Ward and Szabó [1] have shown that a complete graph with N 2 nodes whose edges are colored by at most N colors and at least two colors contains a bichromatic triangle. This fact leads us to a total search problem: Given such a coloring on the complete graph with N 2 nodes, find a bichromatic triangle. Bourneuf et al. [2] have proven that such a total search problem, called Ward-Szabó , is PWPP -hard and belongs to the class TFNP , a class of total search problems in which the correctness of every candidate solution is efficiently verifiable. However, it is open which TFNP subclass contains Ward-Szabó . This paper shows better upper and lower bounds on the computational complexity of Ward-Szabó . We prove that Ward-Szabó is a complete problem for the complexity class PPP , a TFNP subclass of problems in which the existence of solutions is guaranteed by the pigeonhole principle.

One of the most famous TFNP subclasses is PPP , which is the set of all search problems whose totality is guaranteed by the pigeonhole principle. The author's recent preprint [1] has introduced a TFNP problem related to the pigeonhole principle over a quotient set, called Quotient Pigeon , and shown that the problem Quotient Pigeon is not only PPP -hard but also PLS -hard. In this paper, we formulate other computational problems related to the pigeonhole principle over a quotient set via an explicit representation of the equivalence classes. Our new formulation introduces a non-trivial PPP ∩ PPA k -complete problem for every k ≥ 2 . Furthermore, we consider the computational complexity of a computational problem related to Kőnig's lemma, which is a weaker variant of the problem formulated by Pasarkar et al. [2] . We show that our weaker variant is PPAD -hard and is in PPP ∩ PPA . • We have investigated the computational aspects of the pi- geonhole principle over a quotient set. • We have introduced the first PPP ∩ PPA k -complete problem for a positive integer k ≥ 2 . • Consider the computational complexity of a weak variant of a problem related to Kőnig lemma.

Abstract Recently, Pasarkar et al. (2023) have introduced the new $${{\,\mathrm{\texttt{TFNP}}\,}}$$ TFNP subclass called $${{\,\mathrm{\texttt{PLC}}\,}}$$ PLC that contains the class $${{\,\mathrm{\texttt{PPP}}\,}}$$ PPP ; they also have proven that several search problems related to extremal combinatorial principles (e.g., Ramsey’s theorem and the sunflower lemma) belong to $${{\,\mathrm{\texttt{PLC}}\,}}$$ PLC . This paper discusses the complexity of the three generalizations of Constrained Long Choice, a $${{\,\mathrm{\texttt{PLC}}\,}}$$ PLC -complete problem. We first discuss the parallel variant: Given a Long Choice instance and $$\varvec{m}$$ m beginning elements, find $$\varvec{m}$$ m Constrained Long Choice solutions. We show that this variant is $${{\,\mathrm{\texttt{FP}}\,}}_{\Vert }^{{{\,\mathrm{\texttt{PLC}}\,}}}$$ FP ‖ PLC -complete. Next, we discuss the iterative variant: Given a Constrained Long Choice instance, a process function that specifies the next beginning element depending on the current solution, and an iteration parameter $$\varvec{T}$$ T , find $$\varvec{T}$$ T Long Choice solutions satisfying the suitable conditions. We prove that this variant is $${{\,\mathrm{\texttt{FP}}\,}}^{{{\,\mathrm{\texttt{PLC}}\,}}}$$ FP PLC -complete. Finally, we consider the inductive variant, which is an iterative variant with the inductive principle. We prove that the inductive variant is not only $${{\,\mathrm{\texttt{PLC}}\,}}$$ PLC -hard but also $${{\,\mathrm{\texttt{PLS}}\,}}$$ PLS -hard, where the class $${{\,\mathrm{\texttt{PLS}}\,}}$$ PLS is the set of all search problems that are solvable by a local search method. Furthermore, we show that our iterative and inductive variants are closed under the Turing reduction.

In this paper, we consider the complexity of the problem of finding a stable fractional matching in a hypergraphic preference system. Aharoni and Fleiner proved that there exists a stable fractional matching in every hypergraphic preference system. Furthermore, Kintali, Poplawski, Rajaraman, Sundaram, and Teng proved that the problem of finding a stable fractional matching in a hypergraphic preference system is PPAD-complete. In this paper, we consider the complexity of the problem of finding a stable fractional matching in a hypergraphic preference system whose maximum degree is bounded by some constant. The proof by Kintali, Poplawski, Rajaraman, Sundaram, and Teng implies the PPAD-completeness of the problem of finding a stable fractional matching in a hypergraphic preference system whose maximum degree is 5. In this paper, we prove that (i) this problem is PPAD-complete even if the maximum degree is 3, and (ii) if the maximum degree is 2, then this problem can be solved in polynomial time. Furthermore, we prove that the problem of finding an approximate stable fractional matching in a hypergraphic preference system is PPAD-complete.

We have proposed practical torque sensing which utilizes a flexible part of a harmonic drive gear. The sensing technique provides joint torque sensing without reducing stiffness of the robot and changing the mechanical structure of the joints. The characteristics of the torque sensing have been studied under an immovable condition. The dependence of characteristics on the rotational velocity have not been discussed. We describe the characteristics under rotational conditions of the harmonic drive. The experimental results show that the accuracy of the torque sensing under high velocity rotation is 2% of the gear torque capacity.