Many NP-complete problems take integers as part of their input instances. These input integers are generally binarized, that is, provided in the form of the “binary” numeral representation, and the lengths of such binary forms are used as a basis unit to measure the computational complexity of the problems. In sharp contrast, the “unarization” (or the “unary” numeral representation) of numbers has been known to bring a remarkably diferent efect onto the computational complexity of the problems. When no computational-complexity diference is observed between binarization and unarization of instances, on the contrary, the problems are said to be strong NP-complete. This work attempts to spotlight an issue of how the unarization of instances afects the computational complexity of various combinatorial problems. We present numerous NP-complete (or even NP-hard) problems, which turn out to be easily solvable when input integers are represented in unary. We then discuss the computational complexities of such problems when taking unary-form integer inputs. We hope that a list of such problems signifies the structural diferences between strong NP-completeness and non-strong NP-completeness.
1. Background and Quick Overview 1.1. Unary Representations of Integer Inputs The theory of NP-completeness has made great success in providing a plausible evidence to the hardness of target computational problems when one tries to solve them in feasible time. The proof of NP-completeness of those problems therefore makes us turn away from solving them in a practical way but it rather guides us to look into the development of approximation or randomized algorithms.
In computational complexity theory, we often attempt to determine the minimum amount of computational resources necessary to solve target combinatorial problems. Such computational resources are measured in terms of the sizes of input instances given to the problems. Many NP-complete problems, such as tkhneapsack problem, thesubset sum problem, and the integer linear programming problem, concern the values of integers and require various integer manipulations. When instances contain integers, these integers are usually expressed in the form of “binary” representation. Thus, the computational complexities, such as running time or memory space, are measured with respect to the total number of bits used for this representation.
This fact naturally brings us a question of what consequences are drawn when input integers are all provided in “unary” using the unary numeral system instead. How does the unary representation afects the computational complexity of the problems? In comparison to the binary numeral system, the unary numeral system is so distinctive, that we need to heed a special attention in our study on the computational complexity of algorithms.
When input integers given to combinatorial problems are expressed in unary, a simple transformation of the unary expression of input integers to their binary representations makes the original input lengths look exponentially larger than their binary lengths. Thus, any algorithm working with the unarized integer inputs seem to consume exponentially less time than the same algorithm with binarized integer inputs. This turns out to be a quite short-sighted analysis.
We often observe that the use of the unary representation significantly alters the computational complexity of combinatorial problems. However, a number of problems are known to remain NP-complete even after we switch binarized integer inputs to their corresponding unarized ones (see1[, Section 4.2]). Those problems are said tostbreong NP-complete1 and this notion has been used to support a certain aspect of the robustness of NP-completeness notion. Non-strong NP-complete problems are, by definition, quite susceptible to the change of numeral representations of their input integers between the binary representation and the unary representation. It is therefore imperative to study a structural-complexity aspect of those non-strong NP-complete problems when input integers are provided in the form of the unary numeral representation. In this work, we wish to look into the features of such non-strong
Earlier, Cook2[] discussed the computational complexity of a unary-representation analogue of the knapsack problem, calleduntahrey 0-1 knapsack problem (UK), which asks whether or not there is a subset of given positive integers, represented in unary, whose sum matches a given target positive integer. This problem UK naturally falls in NL (nondeterministic logarithmic space) but he conjectured that UK may not be NL-complete. This conjecture is supported by the fact that even an appropriately designed one-way one-turn nondeterministic counter automaton can recognize UK (e.g3.],).[ Jenner [4] introduced a variant of UK whose input integers are given in a “shift-unary” representation, whsehrieft-uanary representation [1 , 1 ] represents the numb e⋅r2 . She then demonstrated that this variant is actually NL-complete. We further expand such a shift-unary representationmtuoltiaple shift-unary representation by allowing a finite series of positive integers andgtenoearal unary (numeral) representation by taking all possible integers, including zero and negative ones. See2S.1ecftoirontheir precise definitions.
Driven by our great interest in the efect of the unarization of inputs, throughout this work, we wish to study the computational complexity of combinatorial problems whose input integers are in part unarized by the unary representation. 1Originally, the strong NP-completeness has been studied in the case where all input inptoelygneormsiaarlley bounded. This case is essentially equivalent to the case where all input integers are given in unary. See a discussion in, e.g., [1, Section 4.2].
LOGCFL = 2NPD3CA
NL = 2N4CA EWPP, EPLP
USVPmax, UCVPmax 1t22PDCA 1t2NPDCA 2N3CA UKEXC
1t2NCA USVPmin UCVPmin 1N6CA
Shift‐UK REG 1t12PDCA
SUK 1t1NPDCA 1t1N2CA
U2PART, UASubSum UBCP
For the succinctness of further descriptions, we hereafter refer to input integers expressed in the unary numeral system uansary-form integers (or more succinctluy,narized integers) in comparison tobinary-form integers (orbinarized integers). 1.2. New Challenges and Main Contributions A simple pre-processing of converting a given unary-form input integer into its binary representation provides obvious complexity upper bounds for target combinatorial problems but it does not seem to be suficient to determine their precise computational complexity.
Our goal is to explore this line of study in order to clarify the roles of the binary-to-unary transformation in the theory of NP-completeness (and beyond it) and cultivate a vast research area incurred by the use of unary-form integers. In particular, we plan to focus on several non-strong NP-complete (or even NP-hard) problems and study how their computational complexities can change when we replace the binary-form input integers to the unary-form ones. Among various types of combinatorial problems taking integer inputs, we look into number problems, graph-related problems, and lattice-related problems. It is desirable for us to determine the precise complexity of each combinatorial problem whose instances are unarized.
A brief summary of our results are illustrated in 1F.igTuhreedetailed explanation of the combinatorial problems and complexity classes listed in this figure will be provided in Sections 2–5. We remark that the underlying machines used to define those complexity classes are all limited to run in polynomial time.
We assume that alplolynomials have nonnegative integer coeficients. Alolglarithms are always taken to the ba2s.eThe notationℤs andℕ denote respectively the set of all integers and that of all nonnegative integers. We furtherℕd+etfinoe beℕ − {0}. As a succinct notation, we use [, ] ℤ to denote thineteger interval {, + 1, … , } for two integersand with ≤ . In particula[r1,, ] ℤ is abbreviated a[s] whenever ≥ 1 . Given ∈ ℕ +, we define the linear order<[] on the set[] × []
as: ( 1, 2) <[] ( 2, 2) if either 1 < 2 or 1 = 2 ∧ 1 < 2. Moreover, ℝ denotes the set of all real numbers. Given a v e=ct(or1, 2, … , ) in ℝ , theEuclidean norm ‖‖ 2 of is given by(∑∈[] 2)1/2 and themax norm ‖‖ ∞ is done by max{| | ∶ ∈ []} , where| ⋅ | indicates the absolute value. Given a ,se()t denotes thpeower set of .
Conventionally, we freely identify decision problems with their associated languages. We write1∗ (as a regular expression) for the set of strings of th1e ffoorrmany ∈ ℕ . For convenience, we define10 to be thempty string . Let1+ denote the se1t∗ − {} . Similarly, we use the notatio0n∗ for{0 ∣ ∈ ℕ} with00 = .
Given a positive intege r, the unary representation of is of the form1 (viewed as a string) compared to its binary representation.
Notice that the l1engisthexoafctly rather tha(n log( + 1)) , which is the length of the binary representatio.nAo ffinite series( 1, 2, … , ) of positive integers is expressed by tmhueltiple unary representation of the form(1 1, 1 2, … , 1 ).
When such an instanc e = (1 1, 1 2, … , 1 ) is given to a machine, we explicitly assume thahtas the form o1f 1#1 2# ⋯ #1 with a designated separator symbo#l. For a series of such instan ces= ( 1, 2, … , ) with = (1 1 , 1 2 , … , 1 ) for ∈ []
and ∈ ℕ+, we further assume thattakes the form of 1 11#1 12# ⋯ #1 1 1 ##1 21#1 22# ⋯ #1 2 2 ## ⋯ ##1 1 #1 2 # ⋯ #1 . Moreover, for any positive integer of the fo rm= ⋅ 2 for nonnegative integ erasnd , a shift-unary representation 2 of is a pair[1 , 1 ], which is diferent from the unary representat1ioonf . The length of [1 , 1 ] is ( + )
but no t . We also use amultiple shift-unary representation , which has the form [[1 1, 1 1], [1 2, 1 2], … , [1 , 1 ]] with the condition th2 a+t1 > 2 for all∈ [ − 1] .
This form represents the numb∑e r=1 ⋅ 2 . We intend to call an input integer by the name of its representation. For this purpose, we call the expr1esasniodn[1 , 1 ] theunary-form (positive) integer (or more succinctly, thunearized (positive) integer) and theshift-unary-form (positive) integer, respectively.
To deal with “general” integers, including zero and negative integers, however, we intend to express such an integeras a unary string by applying the following special encoding function ⟨⋅⟩. Let⟨⟩ = 1 if = 0 ; ⟨⟩ = 2 if > 0 ; and⟨⟩ = 2|| + 1 if < 0 . We define the general unary (numeral) representation of as 1⟨⟩ . In a similar way, ageneral shift-unary representation of− for > 0 is defined as a pair of the for[m1⟨−⟩ , 1⟨⟩ ], where and in ℕ must satisfy= ⋅ 2 . 2.2. Turing Machines and Log-Space Reductions Our interest mostly lies on space-bounded computation. As a basic machine model, we thus use deterministic/nondeterministic Turing machines (or DTMs/NTMs, for short), each of which is equipped with a read-only input tape, a rewritable work tape, and (possibly) a w3rite-once output tape.
The notation L (resp., NL) denotes the collection of all decision problems solvable on DTMs (resp., NTMs) in polynomial time using logarithmic space (or log space, for short). A function resources of running machines. must move to the next blank cell. 2Unlike the unary and binary representations, a positive integer in general has more than one shift-unary representation. In most applications, the choice of such representations does not significantly afect the computational 3A tape is callewdrite-once if its tape head never moves to the left and, whenever it writes a non-blank symbol, it fromΣ∗ toΓ∗ for two alphabeΣtsandΓ is computable in log space if there is a DTM such that, on input , it produce s()
on a write-once output tape||in(
Let 1 and 2 denote two arbitrary languages. We sa y t1 hisaLt-m-reducible to 2 (denoted 1 ≤L 2) if there exists a functio(ncalled a reduction function) in FL such that, f o,r any ∈ 1 if () ∈
2. Given a language family, the notation LO( G) denotes the family of all and (ii)( 2( 1), 2( 2), … , 2( )) = 1, where 2() = 1 if with ∈ Σ∗ for any index∈ [] ∈ 2 and 2() = 0 otherwise.
produces a tupl(e1 1 , 1 2 , … , 1 ) such that ( 1)
Before solving a given problem on an inp(1u t1, 1 2, … , 1 ) of unary-form numbers, it is
often useful to sort all entr(ie1s, 2, … , ) of this input. Let us define the functi o n
making the following behavior: on input of the(1fo1r,1m 2, … , 1 ) with 1, 2, … , ∈ ℕ+,
1 ≥ 2 ≥ ⋯ ≥ and (
=
with
≠ , then < holds. Condition (
There is an occasion where, for a set of shift-unary-form integers [1 1, 1 1], [1 2, 1 2], … , [1 , 1 ], we wish to compute the sum = ∑=1 1 ⋅ 2 and output the binary representation oinf the reverse order. The nota ti on denotes the function that computes this va l u.eThe following lemma is useful.
Lemma 2.1 The functions and
are both in FL.
Those functions will be implicitly used for free when solving combinatorial problems in the subsequent sections.
A one-way determinsitic/nondeterminitic pushdown automaton (or a 1dpda/1npda, for short) is another computational model with a read-once input tape and a standard (pushdown) stack whose operations are restricted to the topmost cceoluln. teAr is a FILO (first in, last out) memory device that behaves like a stack but its alphabet consists only of a “single” symbol, say, 1 except for the bottom mark⊥e.rA one-way nondeterministic -counter automaton (or a counter 1ncta) is a one-way nondeterministic finite automaton (1nfa) equippedcowuintthers. We write 1 NCA to denote the family of all languages recognized by appro-pcroiautneter 1ncta’s running in polynomial time. We further expa nCdA1Nto 1NPD CA by supplementing counters to 1npda’s. These specific machines are calolneed-way nondeterministic -counter pushdown automata (or 1npdcta’s). When tape heads of multi-counter automata and pushdown automata are allowed to move in all directions, we call such polynomial-time machines by 2ncta’s and 2npdcta’s, respectively. With the use of these 2ncta’s and 2npdcta’s, we respectively obtain 2 NCA and 2NPD CA.
An alternating machine must use two groups of inner states: existential states and universal states. We are concerned with the number of times that such a machine switches between existential and universal inner states. When this number is upper-bou n(d e≥d0by) along all computation path s ofon any inpu t , the machine is said to have at mo+s1t alternations. For any ≥ 1 , the complexity clas1sΣ PDCA (resp., 2Σ PDCA) is composed of all languages recognized byone-way (resp., two-way) alternating 1-counter pushdown automata running in polynomial time with at mo stalternations starting with existential inner states. Note that 1Σ1PDCA coincides with 1NPDCA.
The notion ofturns was studied initially by Ginsburg and Span5i]e.r T[urn-restricted counter automata were calrelveedrsal bounded in the past literature. A 1ncta is samidakteo a turn along a certain accepting computation path if the stack height (i.e., the size of stack’s content) changes from nondecreasing to decreasing exactly o1n-tcuer.n A1ncta is a 1ncta that makes at most one turn during each computation. We add the prefix “1t” to express the restriction that every underlying machine makes at most one turn. For example, we write 1t1NCA when all underlying 1ncta’s in the definition of 1NCA are 1-turn 1ncta’s. Similarly, we define, e.g., 1t2NPDCA and 1t2Σ PDCA by requiring all stacks and counters to make at most one turn. It follows that⊆RE1Gt1NCA⊆ 1NCA ⊆ CFL, where REG (resp., CFL) denotes the class of all regular (resp., context-free) languages. Notice=th1NatPDC.FILt also follows that L⊆ LOG(1t1NCA) ⊆ LOG(1NCA) = NL. Conventionally, we write LOGCFL instead of LOG(CFL).
Lemma 2.2 For any ≥ 1 , 2N CA ⊆ NL, 2NPD CA ⊆ LOGCFL, and 2Σ2PD CA ⊆ NP.
Proof Sketch. For any index ∈ ℕ +, we define 2Σ AuxPDATI,SP((), ()) to be the
collection of all decision problems solvabtlweob-yway alternating auxiliary pushdown automata
running within tim(e) using space at most() with at most alternations starting with
existential inner states. Wh=en1 , such machines are succinctly cal2laeudx-npda’s, which
will be used in the proof of Proposit2.i3o.nIt is known tha2tΣ1AuxPDATI,SP( (
Proof Sketch. Following an argument of Mins8k]y, g[iven a log-space NTM (or a log-space
2aux-npda), we first simulate the behavior of(anlog) -space auxiliary work tape by two
stacks whose alphabets are of the f{o0,r1m, ⊥}. Since the heights of such stacks are
upperbounded by( log) , the stacks can be further simulated by multiple counters whose heights
are all(
We remark that Minsky’s method of reducing the number of counters down to two does not
work for machines with few computational resources. Thus, we need to seek other methods.
For this purpose, we review the result9]o, fw[hich makes it possible to simulate two counters
by one counter with the heavy use of an appropriately defined “pairing” function.
Claim 1 [9] There exists a fixed deterministic procedure by which any single move of push/pop
operations on two counters of can be simulated by a series of (
The recursive applications of this simulation procedure eventually reduce the number of counters down to four. If we freely use a stack during the procedure, then we can further reduce the number of counters down to three.
The first part of the proposition then follows by combining the above claim with2.L2e.mma If we use one counter as a stack, then we can further reduce 4 counters to 3 counters. This proves the second part of the proposition. 2 3. Combinatorial Number Problems We study the computational complexity of decision problems whose input instances are composed of unarized positive integers. 3.1. Variations of the Unary 0-1 Knapsack Problem The starting point of our study on the computational analyses of decision problems with unarized integer inputs is tuhneary 0-1 knapsack problem, which was introduced in 1985 by Cook [2] as a unary analogue of tkhneapsack problem.
∘ Instance: (1 , 1 1, 1 2, … , 1 ), where ∈ ℕ + and, 1, 2, … , are all positive integers. ∘ Question: is there a subse tof[] satisfying∑∈ = ?
It seems more natural to view UK as a unary analogue osufbtsehtesum problem, which is closely related to t2-hpeartition problem. Let us consider a unary analogue of this 2-partition problem.
∘ Instance: (1 1, 1 2, … , 1 ), where ∈ ℕ + and 1, 2, … , are all positive integers.
∘ Question: is there a subse tof[] such tha∑t∈ = ∑∈ , where = [] − ?
The original knapsack problem and the subset sum problem are both proven in 1972 by Karp
[10] to be NP-complete. The problems UK and U2PART, in contrast, situated within NL.
Lemma 3.1 (
We further introduce two variants of UK and U2PART, called AmbUK and UASubSum as follows.
Ambiguous UK Problem (AmbUK): ∘ Instance: ((1 1, 1 2, … , 1 ), (1 1, 1 2, … , 1 )),
1, 2, … , , 1, 2, … , are all positive integers. ∘ Question: are there an ind e∈x [] where , ∈ ℕ
+ and and a subse t of[] satisfyin g = ∑∈ ?
∘ Instance: ((1 1, 1 2), (1 1, 1 2, … , 1 )), where ∈ ℕ + and 1, 2, 1, 2, … , are positive
∘ Question: is there a subse tof[] such that1 ≤ ∑∈ ≤ 2?
Lemma 3.2 (
Under two diferent types of log-space reductions, the computational complexities of
is odd, then we se (t) () = (1 , 1 1, … , 1 ).
(
∑∈[] . (a) If = /2 , then we set() =
. (b) If < /2 , then we add a new and set () = (1 1, … , 1 , 1 +1 ). (c) If > /2 , then we exchange between and − and apply (b). Our second goal is to show that U2P≤ALRTUK. Lettin g= to be any fixed rejected input. Otherwise, we s=e t/2 ∑ , if and define stance of AmbUK. We define an L-tt-reduction functioans () = ( Next, we show that AmbUK≤L UK. Let = ((1 1, 1 2, … , 1 ), (1 1, 1 2, … , 1 )) be any in1(), 2(), … , ()) , where () = (1 , 1 1, … , 1 ). Clearly, belongs to FL. We also define a truth ta blaes ( 1, 2, … , ) = ⋁=1 . It then follows t h∈at AmbUK if there exists an inde x∈ [] for which () ∈
UK if ( 1(),
2(), … , ()) = 1 . Therefore, AmbUK≤L UK follows.
(
L UK. Let = ((1 1, 1 2), (1 1, … , 1 )) be any input to UASubSum.
AmbUK by setting = 1 in the definition of AmbUK. since ∉ ifne us define + () = (1 () ∈
If 1 = 2, then the reduction is trivial. In the ca1se>o f2, it sufices to define () = (1, 1
UASubSum. In what follows, we assume t h1at< 2. For any ⊆ [] , we
de = ∑∈ . If []
< 1, then we construc(t) = (
Jenner [4] studied a variant of UK, which we intend to callsbhyift-tuhnaery 0-1 knapsack problem (shift-UK) in order to signify the use of the shift-unary representation. She proved that this problem is actually NL-complete.
∘ Instance: [1 , 1 ] and a series([1 1, 1 1], [1 2, 1 2], … , [1 , 1 ]) of nonnegative integers represented in shift-unary, whe r, e 1, 2, … , are all positive integers a,n1d, 2, … , are all nonnegative integers. ∘ Question: is there a subse tof[] such tha∑t∈ 2 = 2 ?
In a similar way, we can define the shift-unary representation versions of AmbUK, UASubSum, and U2PART, denoted by shift-AmbUK, shift-UASubSum, and shift-U2PART, respectively.
Lemma 3.4 The problem shift-UK is in 1N6CA.
Proposition 3.5 shift-UK ≡L shift-U2PART ≡L shift-AmbUK ≡L shift-UASubSum. can be similarly handled.
We abbreviate the se{sthift-U2PART,shift-AmbUK, shift-UASubSum} as .
It is easy to obtain, by modifying the proof of Propos3i.t3i,otnhat shift-UK≤L for any ∈ . To show that≤ L shift-UK for an y∈ , it sufices to show tha t belongs to NL because the L-m-completeness of shift-U4K] g[uarantees that≤ L shift-UK. In the case of =
shift-UASubSum, we consider the following algorithm. On input of the form (([1 1, 1 1], [1 2, 1 2]), ([1 1, 1 1], … , [1 , 1 ])), we nondeterministically choose a num ∈be[r] and indice s1, 2, … , ∈ [] and check th at12 1 ≤ ∑∈ 2 ≤ 22 2. Note that, by Lemma2.1, the sum∑∈ 2 can be computed using only log space. Hen cei,s in NL. The other cases given as a set of pairs 2 2
Corollary 3.6 The problems shift-U2PART, shift-AmbUK , and shift-UASubSum are all NLcomplete.
For later references, we introduce another variant of UK. This variant requires a prohibition of certain successive choices of unarized integer inputs.
UK with Exception (UKEXC): ∘ Instance: (1 , 1 1, 1 2, … , 1 ) and ⊆ {(, ) ∣ , ∈ [], < }
(1 , 1 ), where ∈ ℕ + and, 1, 2, … , are inℕ+. ∘ Question: is there a subse t= { 1, 2, … , } of[] with ∈ ℕ + and 1 < 2 < ⋯ < such that (i∑) ∈ = and (ii) no ∈ [ − 1] satisfies ( , +1 ) ∈ ? Note that, wh e n= ∅
, UKEXC is equivalent to UK.
Lemma 3.7 UKEXC is in 2N3CA. choice, say,1 satisfies (, )
∉ pop 1 for the chosen indic e.s
We nondeterministically cho1o seby reading an input from left to right. We use two counters to remember the in d(ienxthe form o1f ) for checking that the next possible . The third counter is used to st1oraend then sequentially We also introduce another variant of UK, which concerns simultaneous handling of input Simultaneous Unary 0-1 Knapsack Problem (SUK): ∘ Instance: (1 1, 1 11, 1 12, … , 1 1 ), … , (1 , 1 1 , 1 2 , … , 1 ), where, ∈ ℕ + and and ( ∈ [], ∈ []
) are all positive integers. ∘ Question: is there a subse t⊆ [] such tha∑t∈ = for all indice∈s [] ?
The complexity class 11Σt2PDCA is the one-way restriction ofΣ21PtD2CA.
Lemma 3.8 The problem SUK is in 1t1Σ2PDCA.
To recognize SUK, let us consideronae-way alternating counter pushdown automaton (or a 1apdcta) that behaves as follows.
Given an inpouftthe form (1 1, 1 11, 1 12, … , 1 1 ), … , (1 , 1 1 , 1 2 , … , 1 ), we call each segmen(t1 , 1 1 , 1 2 , … , 1 ) of by the th block of .
In existential inner states, we first choose a st∈ri{n0,g1} ∗ and push it into a stack, where = 1 2 ⋯ indicates that, for an∈y[] , we select th eth entry from every block exactly when = 1. Let
= { ∈ [] ∣ = 1}. In universal inner states, we then check whether = ∑∈ holds for al∈l [] . This last procedure is achieved by first stor1i nginto a counter. As popping the valu esone by one from the stack, ∈if , then we decrease the block(1 1 , … , 1 ) of is finished, if the stack is empty and the counter beco0m, etshen we counter b y . Otherwise, we do nothing. When either the stack gets empty or the assigned accept ; otherwise, we reje ct. Note that the stack and the counter make only 1-turns and the input-tape head moves only in one direction. 2 and1 for ∈ ℕ +
. 1 2 ⋯ = 1 2 ⋯ ?
3.2. Unary Bounded Correspondence Problem We turn our attention tobtohuneded Post correspondence problem (BPCP), which is a wellknown problem of determining whether, given a{(s e, t number ≥ 1 , a certain sequenc(e1, 2, … , ) of elements in[] )}∈[]
of binary string pairs and a with ≤ satisfies 1 2 ⋯ = and by unary strings, we obtain the following “unary” variant of PCP. 1 2 ⋯ . This problem is known to be NP-complet1e1][. When we replace binary stri ngs
∘ Instance: (( 1, 1), ( 2, 2), … , ( , )) for unary strin gs1, 2, … , , 1, 2, … , ∈ 1+ ∘ Question: is there a sequenc(e 1, 2, … , ) of elements in[] with ∈ [] satisfying ∑∈ | | = ∑∈
| |, where| | and| | mean the lengths of stringasnd , respectively.
Since and are unary strings, the above require men⋯t 1 = 1 ⋯ is equivalent to Lemma 3.9 UBCP belongs to 1t1N2CA.
Proposition 3.10 UK ≤L UBCP ≤L AmbUK .
Proof Sketch.
L
Here, we only show the last reduction UB≤CP AmbUK. Let = (( 1, 1), … , ( , )) be any instance to UBCP. Assume that, for a∈n[y] , = 1 and = 1 for certain number s, ∈ ℕ+. Let = max{∑∈[] , ∑∈[] }. Note tha|t|≤ ∑∈ ≤ and || ≤
∑∈ ≤ for any ⊆ [] . We then se t = − ( − ) for eac h∈ [] . We remark that ∑∈ = || − ( ∑∈ − ∑∈ ) ≥ || − ( − ||) = (|| − 1) + || ≥ 0 for any nonempty subset of[] . If ∈
UBCP, then there is a nonempty se⊆t [] such that∑∈ = ∑∈ , that is∑,∈ ( − ) = 0. It then follows th∑a∈t = || .
We also check i∑f∈[] = ∑∈[] or if 0 = 0 for a certain inde0x∈ [] . If this is true, then we know tha=t [] or{ 0}. Otherwise, we se t = ⋅ for eac h∈ [2, − 1] ℤ and then define = ((1 2, 1 3, … , 1 −1 ), (1 1, 1 2, … , 1 )). It follows th a∈t UBCP if ∈ AmbUK. 2 Corollary 3.11 UK ≡L UBCP.
We look into decision problems that are related to graphs, in particular, weighted graphs in which either vertices or edges are labeled with “weights”. Here, we study the computational complexity of these specific problems.
We begin with edge-weighted path problems, in which we search for a simple path whose weight matches a target unarized number, which is given in unary. We consider, in particular, directed acyclic graphs (or dags) whose edges are further labeled with weights, which are given in unary.
For the purpose of this work, a da=g ( , ) given as part of inputs to an underlying machine is assumed to satisfy thaits a subset ofℕ+, e.g., = { 1, 2, … , } for 1, 2, … , ∈ ℕ+. We also use the following specific encoding o.f Given a verte x, we write[] When [] for the set of all adjacent vertices enterin g, nfraommely, { ∈ ∣ (, ) ∈ } .
equals{ 1, 2, … , } with 1 < 2 < ⋯ < , we express it in the “multi-unary” ((1 1, 1 1,1, 1 1,2, … , 1 1, 1 ), … , (1 , 1 ,1, 1 ,2, … , 1
form of(1 , 1 1, 1 2, … , 1 ). The unary adjacency list representation 1 < 2 < ⋯ < and[ ] = { ,1, ,2, … , , } with ,1 < ,2 < ⋯ < ,
for any ∈ [] . , )) with ∈ ℕ if = { 1, 2, … , } with of is of the form Edge-Weighted Path Problem (EWPP) ∘ Instance: a dag = ( , )
with ⊆ ℕ + given in the form o f given as1 , edge weights(, ) ∈ ℕ + given as1(,)
for all edge(s,) ∈ , and1 with ∈ ℕ +, provided that edges are enumerated according to the linea<r[]o.rder ∘ Question: is there a vert ex∈ such that the total edge weight of a pathtforom , a vertex ∈ In comparison, thgeraph connectivity problem for directed “unweighted” graphs (DSTCON) When each edge weight 1is,the total weight of a path is the same as the length of the path. This fact makes us introduce another decision problseimnk. Aof a directed graph is a vertex is known to be NL-complete12[].
Lemma 4.1 EWPP is in NL. of outdegre0e in the graph.
∘ Instance: a dag = ( , ) 1 with ∈ ℕ +.
with ⊆ ℕ + given as , a verte x∈ given as1 , and ∘ Question: is there a sink of such that a path fromto has length exact l?y Proposition 4.2 EWPP ≡L EPLP.
Firstly, we show that EPL≤PL EWPP. Given an instance= (, , 1 ) of , we define another instance, sa y,of EWPP as follows. For every leaf of , we add a new verte x̄ and a new edge(, )̄ to and obtain the new vertex se′t and the new edge s et′. Consider the resulting gr ap′h= ( ′, ′). Let = | ′|. We define (, ) = 1 for all pair(s,) ∈
and additionally we s(e, t)̄ = + 1 Let ′ = + + 1 . We define = ( ′, {()} ∈ ′, 1 ′). We want to verify that (∈*) EPLP if for any old lea∈f . ∈ EWPP.
To prove (*), let us assume tha∈t EPLP. We then take a lengthpa-th = ( 0, 1, … , ) of with 0 = and is a leaf. Conside rand (+) = ( 0, 1, … , , ̄ ). The total weight o(+f) in ′ is + (
, ̄ ) = + + 1 = ′. Hence, is in EWPP. Conversely, assume tha∈t EWPP = | ′|, must include a leaf. Hence,must be −̄1 . Moreover,− 1 = and consider a pat h= ( 0, 1, … , ) of ′ with 0 = satisfying∑=0 ( , +1 ) = ′. Since follows. The path (−) = ( 0, 1, … , −1 ) is a path fro m to a leaf o f and its length is exact.lyThis implies tha t∈
Secondly, we show that EWPP≤L
EPLP. Let = (, , {()} stance of EWPP.
We construct an instance of EPLP as follows. with (, ) = 1 , we introduc e + 1 extra vertice{s, ̄ ∈ , 1 ) be any in
Fo(r, )ea∈ch 1′, 2′, … , ′} and extra edges {(, 1′), ( 1′, 2′), … , (
′, +′1 ), ( ′, ), ( ′, )̄ ∣ ∈ [ − 2]} . Those edges form two paths from to and to ̄ of length exact l.yNotice tha t̄becomes a new leaf. L et′ and ′ denote the extended sets of and , respectively, and s et′ = ( ′, ′). For the instan ce= ( ′, , 1 ), it is possible to prove tha∈t EWPP if ∈ EPLP.
Proposition 4.3 EWPP and EPLP are both L-m-complete for NL. 2 if 2 (
, 1 , 1||+2 ) ∈ EPLP.
Proof Sketch.
Here, we wish to prove (*≤) L EPLP for any langua gein 1NCA. If this is true, then all languages in NL are L-m-reducible to EPLP sin(c1eNLCOAG) = NL. Moreover, since EWPP belongs to NL by Lemma4.1, EPLP is also in NL. Therefore, EPLP is L-m-complete for NL. Since EWPP≡L EPLP by Proposition4.2, we also obtain the NL-completeness of
To show the statement (*), let us take any 1ncatnad consider surface configurations of on input . Note that, since surface configurations have(silzoeg||) , we can express them as unary-form positive integers. Between two surface configurations, we define a single-step transition relat⊢io n. We then define a computation grap h = ( , ) of on the input . The vertex set is composed of all possible surface configuration s oofn . We further define to be the set of all pa(ir1s, 2) of surface configurations satisfyin1g⊢ 2. The root of is set to be the initial surface configuration. oItfthen follows th∈at()
Let us argue how EWPP is related to UKEXC and UK. To see the desired relationships,
we introduce two restricted variants of EWPP. We say th at= a( , d)ag
with ⊆ ℕ + is
topologically ordered if, for any two vertic,e∈s
, (, ) ∈
implies < . We define TO-EWPP
as the restriction of EWPP onto instances that are topologically orde r=ed(., )A dagis
edge-closed if, for any three vertic,e,s∈
, (
Proposition 4.4 (
L TO-EWPP. (, , {1 ()
}∈ , 1 ) with = ( , ) TO-EWPP. Given an instance = ((1 , 1 1, … , 1 ), ) sociated instance, sa y,of TO-EWPP as follows. We then defin e= {,
In what follows, we focus only on (
Assume that = is any instance of TO-EWPP. An associated inst ance of UKEXC is constructed as follows. Firstly, we assume tishatcyclic because, otherwise, we conver t to an acyclic grap h′ = ( ′, ′) by setting ′ = {((, ) ∣ ∈ [| |], ∈ } and ′ = {((, ), ( + 1, )) ∣ ∈ [| | − 1], (, ) ∈ } . For simplicity, we further assume that = [2, ] ℤ and is vertex2. We define an encoding ⟨, ⟩ of two distinct verti,c e∈s [] as ⟨, ⟩ = ( − 1) +
. We consider only a unique connected component incl udbiencgause any other connected component is irrelevant. Hereafter, we assume that this connected component contains all vertice s .inWe expand to ′ = ( ′, ′) by settin g ′ = ∪ {1} and ′(1, ) = ∗ + 1 for any ∈ [2, ] ℤ, where ∗ = ∑(,)∈ (, ) . ′ = ∪ {(1, ) ∣ ∈ [2, ]
ℤ}. As for new weights, we set′(, ) = (, ) We further s et⟨,⟩ = (, )
if (, ) ∈ . Moreover, let⟨1,⟩ = ∗ + 1 for any ∈ [2, ] ℤ.
For any other pai(r,) , the value⟨,⟩ is not defined. Let denote the set of a⟨l,⟩l ’s that are defined. Assume that has the form{ 1 We write for the se{t1, 2, … , }. The set sets: {(⟨, ⟩, ⟨ ′, ′⟩) ∣ , , ′, ′ ∈ [], (⟨, ⟩ ≮ ⟨ , 2, … , } with ≤ 2, where 1 < 2 < ⋯ < .
is defined to be the union of the following ′, ′⟩ ∨ ≠ ′ ∨ = ′), (, ) ∈ , ( ′, ′) ∈ } , {(⟨, ⟩, ⟨ ′, ′⟩) ∣ , ′, , ′ ∈ [], ⟨, ⟩ < ⟨ ′, ′⟩, ((, ) ∉ ∨ ( ′, ′) ∉ )} , and{(⟨, ⟩, ⟨1, ′⟩) ∣ , , ′ ∈ for any(, ) ∈ and [2, ] ℤ}. Let = +
We define the desired instanc e as = ((1 , 1 1 , 1 2 , … , 1 ), ) . For this instan ce, we can prove th at∈ TO-EWPP if ∈ UKEXC. 2
Let us discuss lattice problemsl.aAttice is a set of integer linear combinations of basis vectors. Here, we deal only with the case where bases are takenℤfrfoomr a certa in∈ ℕ + . The decision version of thcleosest vector problem (CVP) is known to be NP-complete13[]. We then consider a variant of CVP. To fit into our setting of unary-form integers, a simple norm notion of thmeax norm ‖ ⋅ ‖∞ from Section2.1. In a syntactic similarity, we further introduce the notatio‖n‖ min to express mi n{| | ∶ ∈ []}
for any real-valued vecto=r( 1, 2, … , ).
Notice tha‖t‖ min does not serve as a true “distance”. For conveni(enc1,e ,2, … , ) denotes the lattice spanned by a given{se1,t 2, … , } of basis vectors.
Unary Max-Norm Closest Vector Problem (UCVPmax): ∘ Instance: 1 for a positive integ e r, a tuple(1⟨ [1]⟩, 1⟨ [2]⟩, … , 1⟨ []⟩ ) for a set { 1, 2, … , } of lattice bases with =
( [1], [2], … , []) ∈ (1⟨ 0[1]⟩, 1⟨ 0[2]⟩, … , 1⟨ 0[]⟩ ) for a target vec to0r= ( 0[1], 0[2], … , 0[]) ∈ ℤ . ℤ , and a tuple ∘ Question: is there a lattice vec toinr ( 1, 2, … , ) such that the max nor‖m− 0‖∞ is at mos t ? In the above definition of UCVmPax, we replace‖ ⋅ ‖∞ by ‖ ⋅ ‖ and then obtain UCVmiPn.
For simplicity, in what follows, we intend to w̄ froitre(1⟨[1]⟩ , 1⟨[2]⟩ , … , 1⟨[]⟩ ) if =
U2PART, called thseimultaneous unary 2 partition problem (SU2PART). It is possible to prove
Let = ( 1, 2, … , ) with = (1 1 , 1 2 , … , 1 ) for any ∈ [] that SUK≤L SU2PART. It therefore sufices to verify that SU2PA≤RLT UCVPmax. SU2PART. Let = ∑∈[] for each ∈ [] and set and ∈ [] , we further s e t′ = and ′ = = max∈[]
{ }. Given any
. Let us define vectors
1, 2, … , as 1 = ( 1′1, 2′1, … , 1′ , 2, 0, 0, … , 0), 2 = ( 2′1, 2′2, … , 2′ , 0, 2, 0, … , 0), …, =
( 1′ , 2′ , … , ′ , 0, 0, 0, … , 0, 2). Moreover, we set0 = (⌊ 1′
/2⌋, ⌊ 2′/2⌋, … , ⌊ ′ /2⌋, 1, 1, … , 1) and
= 1 . We then define to be(1 , 1̄, 2̄, … , ̄ , 0̄). Clearly , is an instance of UCSmPax. It then
be any instance of
follows tha∈t U2PART if ∈ UCVCmax.
2
Lemma 5.2 (
It is not clear that UCmVaxPbelongs to 1t2NPDCA or even P.
Next, we look into another relevant problem, known sahsorttheset vector problem. We consider its variant.
Unary Max-Norm Shortest Vector Problem (USVPmax):
of lattice bases w i th= ( [1], [2], … , []) ∈ ℤ . ∘ Instance: 1 with ∈ ℕ + and a tuple(1⟨ [1]⟩, 1⟨ [2]⟩, … , 1⟨ []⟩ ) for a set{ 1, 2, … , } ∘ Question: is there a “non-zero” lattice vectoinr ( 1, 2, … , ) such that the max norm ‖‖ ∞ is at mos t ?
Similarly, we can define USVPmin by replacing‖ ⋅ ‖∞ with‖ ⋅ ‖min. In a way similar to prove Lemma 5.2, we can prove that USVmPax ∈ 1t2Σ2PDCA. Moreover, the following relations hold. Lemma 5.3 USVPmin ≤L UCVPmin and USVPmax ≤L UCVPmax.
We do not know if USVmPin ≡L UCVPmin and USVPmax ≡L UCVPmax.