Does Subset Sum Admit Short Proofs?
Michał Włodarczyk


Use of triplet loss for facial restoration in low-resolution images
    Sebastián Pulgar, Domingo Mery 
        
This work is supported byFondecyt-Chile 1191131 and National Center for Artificial Intelligence CENIA FB210017, Basal ANID, partly supported this work.

    September 9, 2024
=====================================================================================================================================================================================================



§ ABSTRACT 
    
    We investigate the question whether Subset Sum can be solved by a polynomial-time algorithm with access to a certificate of length poly(k) where k is the maximal number of bits in an input number. 
    In other words, can it be solved using only few nondeterministic bits?

    
    
    
    
    This question has motivated us to initiate a systematic study of certification complexity of parameterized problems.  
    Apart from Subset Sum, we examine problems related to integer linear programming, scheduling, and group theory.
    We reveal an equivalence class of problems sharing the same hardness with respect to having a polynomial certificate.
    These include Subset Sum and Boolean Linear Programming parameterized by the number of constraints.
    Secondly, we present new techniques for establishing lower bounds in this regime.
    In particular, we show that Subset Sum in permutation groups is at least as hard for nondeterministic computation as 3Coloring in bounded-pathwidth graphs. 




§ INTRODUCTION


Nondeterminism constitutes a powerful lens for studying complexity theory.
The most prominent instantiation of this concept is the class NP 
capturing all problems with solutions checkable in polynomial time.

Another well-known example is the class NL of problems that can be solved nondeterministically in logarithmic space <cit.>.
But the usefulness of nondeterminism is not limited to merely filtering candidates for deterministic classes.
A question studied in proof complexity theory is how much nondeterminism is needed to solve certain problems or, equivalently, how long proofs have to be to prove certain theorems <cit.>.
Depending on the considered logic, these theorems may correspond to instances of problems complete for NP <cit.>, coNP <cit.>, or W[SAT] <cit.>.
The central goal of proof complexity is to
establish lower bounds for increasingly powerful proof systems in the hope of building up techniques to prove, e.g., NP  coNP. 



What is more, there are connections between nondeterministic running time lower bounds and fine-grained complexity <cit.>.



In the context of online algorithms, nondeterminism is used to measure how much knowledge of future requests is needed to achieve a certain performance level <cit.>.

Bounded nondeterminism plays an important role in organizing parameterized complexity theory.
The first class studied in this context was W[P] comprising parameterized problems solvable in FPT time, i.e., f(k)·(n), when given access to f(k)·log(n) nondeterministic bits <cit.>.
In the last decade, classes defined by nondeterministic computation in limited space have attracted significant attention <cit.> with a recent burst of activity around the class XNLP <cit.> of problems solvable in nondeterministic time f(k)·(n) and space f(k)·log(n).

While the study of W[P] and XNLP concerns problems considered very hard from the perspective of FPT algorithms, a question that  has eluded a systematic examination so far 
is how much nondeterminism is necessary to solve FPT problems in polynomial time. 
A related question has been asked about the amount of nondeterminism  needed to solve d-CNF-SAT in sub-exponential time <cit.>.


To concretize our question,
we say that a parameterized problem P admits a polynomial certificate if an instance (I,k) can be solved in polynomial time when given access to (k) nondeterministic bits[It is more accurate to say that a “certificate” refers to a particular instance while a problem can admit a “certification”. We have decided however to choose a shorter and more established term. We also speak of “certificates” instead of “witnesses” because “witness” sometimes refers to a concrete representation of a solution for problems in NP, see e.g., <cit.>.].
For example, every problem in NP admits a polynomial certificate under parameterization by the input length.
This definition captures, e.g., FPT problems solvable via branching as a certificate can provide a roadmap for the correct branching choices.
Furthermore, every parameterized problem that is in NP and admits a polynomial kernelization has a polynomial certificate given by the NP certificate for the compressed instance.
The containment in NP plays a subtle role here: Wahlström <cit.> noted that a polynomial compression for the K-Cycle problem is likely to require a target language from outside NP exactly because K-Cycle does not seem to admit a polynomial certificate.

In this article we aim to
organize the folklore knowledge about polynomial certification into a systematic study, provide new connections, techniques, and motivations,
and lay the foundations for a hardness framework.




    When is certification easy or hard?

The existence of a certificate of size p(k) = (k) entails an FPT algorithm with running time 2^p(k)(n),  
by enumerating all possible certificates. We should thus restrict ourselves only to problems solvable within such running time.
On the other hand, when such an algorithm is available then one can solve the problem in polynomial time whenever p(k) ≤log n.
Therefore, it suffices to handle the instances with log n < p(k). 
Consequently, 
for such problems it is equivalent to ask for a certificate of size (k+log n) as this can be bounded polynomially in k via the mentioned trade-off (see <Ref>).
This observation yields polynomial certificates for problems parameterized by the solution size, such as Multicut <cit.> or Planarization <cit.>, which do not fall into the previously discussed categories.

What are the problems solvable in time 2^k^(1)n^(1) yet unlikely to admit a polynomial certificate?
The Bandwidth problem has been conjectured 
not be belong to W[P] because one can merge multiple instances into one, without increasing the parameter, in such a way that the large instance is solvable if and only if all the smaller ones are.
It is conceivable that a certificate for the large instance should require at least one bit for each of the smaller instances, hence it cannot be short <cit.>.
The same argument applies to every parameterized problem that admits an AND-composition, a construction employed to rule out polynomial kernelization <cit.>, which effectively encodes a conjunction of multiple 3SAT instances as a single instance of the problem.
Such problems include those parameterized by graph width measures like treewidth or pathwidth, and it is hard to imagine polynomial certificates for them.
However, kernelization hardness can be also established using an OR-composition, which does not stand at odds with polynomial certification. 

The close connection between AND-composition and polynomial certificates has been observed

by Drucker, Nederlof, and Santhanam <cit.>
who focused on parameterized search problems solvable by
One-sided Probabilistic Polynomial (OPP) algorithms (cf. <cit.>).
They asked which problems admit an OPP algorithm that finds a solution with probability 2^-(k).

This may seem much more powerful than using (k) nondeterministic bits but the success probability can be replaced by Ω(1) when given a single access to an oracle solving k-variable Circuit-SAT <cit.>. 
A former result of Drucker <cit.> implies that an OPP algorithm with success probability 2^-(k) (also called a polynomial Levin witness compression) for a search problem admitting a so-called constructive AND-composition would imply  <cit.>.















    Constructive vs. non-constructive proofs.


The restriction to search problems is crucial in the work <cit.> because 
the aforementioned hardness result does not apply to algorithms that may
recognize yes-instances without constructing a solution explicitly but by proving its existence in a non-constructive fashion.
As noted by Drucker <cit.>, his negative results do not allow to rule out this kind of algorithms.

In general, search problems may be significantly harder than their decision counterparts.
For example, there are classes of search problems for which the solution is always guaranteed to exist (e.g., by the pigeonhole principle, in the case of class PPP <cit.>) but the existence of a polynomial algorithm computing some solution is considered unlikely.
For a less obvious example, consider finding a
non-trivial divisor 
of a given integer n.
A polynomial (in log n) algorithm finding a solution could be used to construct the factorization of n, resolving a major open problem.
But the existence of a solution is equivalent to n being composite and this can be verified in polynomial time by the AKS primality test <cit.>.


As yet another example, consider the problem of finding a knotless embedding of a graph, i.e., an embedding in ℝ^3 in which every cycle forms a trivial knot in a topological sense.
The class 𝒢 of graphs admitting such an embedding is closed under taking minors so Robertson and Seymour's Theorem ensures that 𝒢 is characterized by a finite set of forbidden minors <cit.>, leading to a polynomial algorithm for recognizing graphs from 𝒢.
Observe that excluding all the forbidden minors yields a non-constructive proof that a knotless embedding exists.
On the other hand, the existence of a polynomial algorithm constructing such an embedding remains open <cit.>.


To address this discrepancy, we propose the following conjecture which asserts that not only finding assignments to many instances of 3SAT requires many bits of advice but even certifying that such assignments exist should require many bits of advice.
We define the parameterized problem where an instance consists of a sequence of n many 3SAT formulas on k variables each, and an instance belongs to the language if all these formulas are satisfiable. We treat k as a parameter.


     does not admit a polynomial certificate unless .


Observe that is solvable in time 2^k·(k)· n, so the questions whether it admits a certificate of size (k), (k)·log n, or (k + log n) are equivalent.
We formulate <Ref> as a conditional statement because we believe that its proof in the current form is within the reach of the existing techniques employed in communication complexity and kernelization lower bounds <cit.>.
Then the known examples of AND-composition could be interpreted as reductions from that justify non-existence of polynomial certificates.






 §.§ The problems under consideration



    Our focus: Subset Sum.


In Subset Sum we are given a sequence of n integers (also called items), a target integer t (all numbers encoded in binary), and we ask whether there is a subsequence summing up to t.
This is a fundamental NP-hard problem that can be solved in pseudo-polynomial time (tn) by the classic algorithm by Bellman from the 50s <cit.>.
In 2017 the running time has been improved to (t+n) by Bringmann <cit.>.
Subset Sum reveals miscellaneous facets in complexity theory: it has been studied from the perspective of exponential algorithms <cit.>, logarithmic space <cit.>, 
approximation <cit.>, kernelization <cit.>, fine-grained complexity <cit.>, 
cryptographic systems <cit.>, and average-case analysis <cit.>.
Our motivating goal is the following question.


    Does Subset Sum admit a polynomial certificate for parameter k = log t?



From this point of view, the pseudo-polynomial time (tn) can be interpreted as FPT running time (2^kn).
It is also known that a kernelization of size (k) is unlikely <cit.>.
Observe that we cannot hope for a certificate of size o(log t) because the algorithm  enumerating all possible certificates would solve Subset Sum in time 2^o(log t)n^(1) = t^o(1)n^(1) contradicting the known lower bound based on the Exponential Time Hypothesis (ETH) <cit.>.




The parameterization by the number of relevant bits exhibits a behavior different from those mentioned so far, that is, width parameters and solution size, making it an uncharted territory for nondeterministic algorithms.
 The study of was suggested by Drucker et al. <cit.>  in the context of polynomial witness compression.
These two directions are closely related yet ultimately
incomparable: the requirement to return a solution makes the task more challenging but the probabilistic guarantee is less restrictive than constructing a certificate.

However, establishing hardness in both paradigms boils down to finding

a reduction of a certain kind from AND-3SAT[k].



The density of a Subset Sum instance is defined as n  / log(t) in the cryptographic context <cit.>.
As it is straightforward to construct a certificate of size n, we are mostly interested in instances of high density, which also appear hard for exponential algorithms <cit.>.
On the other hand, instances that are very dense enjoy a special structure that can be leveraged algorithmically <cit.>.
The instances that seem the hardest in our regime are those in which n is slightly superpolynomial in log t. 
Apart from the obvious motivation to better understand the structure of Subset Sum, we believe that the existence of short certificates for dense instances could be valuable for cryptography. 

There are several other studied variants of the problem. In Unbounded Subset Sum the input is specified in the same way but one is allowed to use each number repeatedly.
Interestingly, this modification enables us to certify a solution with 
 (log^2 t) bits (<Ref>).
Another variant is to replace the addition with some group operation.
In Group-G Subset Sum we are given a sequence of n elements from G and we ask whether one can pick a subsequence whose group product  equals the target element t ∈ G.
Note that we do not allow to change the order of elements when computing the product what makes a difference for non-commutative groups. 
This setting has been mostly studied for G being the cyclic group _q <cit.>.
To capture the hardness of an instance, we choose the parameter to be log |G| (or equivalent).
In particular, we will see that Group-_q Subset Sum[log q] is equivalent in our regime to .
We will also provide examples of groups for which certification is either easy or conditionally hard. 



    Integer Linear Programming.

We shall consider systems of equations in the form {Ax=b | x ∈{0,1}^n} where A ∈^m × n, b ∈^m, with the parameter being the number of constraints m.
This is a special case of Integer Linear Programming (ILP) over boolean domain, known in the literature as  pseudo-boolean optimization.
This case has been recognized as particularly interesting by the community working on practical ILP solvers because pseudo-boolean optimization can be treated with SAT solvers <cit.>.
It is also applicable in the fields of approximation algorithms <cit.> and election systems <cit.>.
Eisenbrand and Weismantel <cit.> found an elegant application of Steinitz Lemma to this problem and gave  
an FPT algorithm
with running time (||A||_∞ + m)^(m^2)· n (cf. <cit.>).

For simplicity we will consider variants with bounded ||A||_∞.
In the 0-1 ILP problem we restrict ourselves to matrices A ∈{-1,0,1}^m × n and in  Monotone 0-1 ILP we consider A ∈{0,1}^m × n.
A potential way to construct a short certificate would be to tighten the proximity bounds from <cit.> for such matrices: find an extremal solution x^* to the linear relaxation  {Ax=b | x ∈ [0,1]^n} and hope that some integral solution z lies nearby, i.e., ||z-x^*||_1 ≤(m).
This however would require tightening the bounds on the vector norms in the  Graver basis of the matrix A.
Unfortunately, there are known lower bounds making this approach hopeless <cit.>.

It may be tempting to seek the source of hardness in the large values in the target vector b.
We will see however that the problem is no easier when we assume b=0 and look for any non-zero solution. 
We refer to such problem as 0-Sum 0-1 ILP.

A special case of Monotone 0-1 ILP is given by a matrix A ∈{0,1}^m × n with n = md columns corresponding to all size-d subsets of {1,…,m}.
Then Ax = b has a boolean solution if and only if b forms a degree sequence of some d-hypergraph, i.e., it is d-hypergraphic.
There is a classic criterion by Erdős for a sequence to be graphic <cit.> (i.e., 2-hypergraphic) but already for d=3 deciding if b is d-hypergraphic becomes NP-hard <cit.>.
It is straightforward to certify a solution with m^d bits, what places the problem in NP for each fixed d, but it is open whether it is in NP when d is a part of the input (note that the matrix A is implicit so the input size is (mdlog m)).
This basically boils down to the same dilemma: can we certify the existence of a boolean ILP solution x  without listing x in its entirety?

There is yet another motivation to study the certification complexity of 0-1 ILP.
If this problem admits a certificate of size (m) then any other problem that can be modeled by 0-1 ILP with few constraints must admit a short certificate as well.
This may help classifying problems into these that can be solved efficiently with ILP solvers and those that cannot.




    Other problems parameterized by the number of relevant bits.


A classic generalization of Subset Sum is the Knapsack problem where each item is described by a size p_i and a weight w_i; here we ask for a subset of items of total weight at least w but total size not exceeding t. 
Following Drucker et al. <cit.> we parameterize it by the number of bits necessary to store items' sizes and weights, i.e., log(t + w).
The need to process weights makes Knapsack harder than Subset Sum from the perspective of fine-grained complexity <cit.> but they are essentially equivalent on the ground of exponential algorithms <cit.>.
We will see that they are equivalent in our regime as well. 

We will also consider the following scheduling problem which is in turn a generalization  of Knapsack.
In Scheduling Weighted Tardy Jobs
we are given a set of n jobs, where each
job j ∈ [n] has a processing time p_j ∈, a weight w_j ∈, and a due date d_j ∈. 
We schedule the jobs on a single machine and we want to minimize the total weight of jobs completed after their due dates (those jobs are called tardy).


Equivalently, we try to maximize the total weight of jobs completed in time.


In the scheduling literature, Scheduling Weighted Tardy Jobs is referred to as 1 || ∑ w_jU_j using Graham’s notation.
The problem is solvable in pseudo-polynomial time  (n· d_max) by the classic Lawler and Moore's algorithm <cit.>.

The interest in 1 || ∑ w_jU_j has been revived due to the recent advances in fine-grained complexity
<cit.>. 

Here, the parameter that captures the number of relevant bits is 
log (d_max + w_max).



 §.§ Our contribution



The standard polynomial parameter transformation (PPT) is a polynomial-time reduction between parameterized problems that maps an instance with parameter k to one with parameter k' = (k).
We introduce the notion of a nondeterministic polynomial parameter transformation (NPPT) which extends PPT by allowing the reduction to guess (k) nondeterministic bits.
Such reductions preserve the existence of a polynomial certificate.

We write P ≤_nppt Q (resp. P ≤_ppt Q) to indicate that P admits a NPPT (resp. PPT) into Q.

We demonstrate how NPPT help us organize the theory of polynomial certification, similarly as  PPT come in useful for organizing the theory of Turing kernelization <cit.>. 
As our first result, we present an equivalence class of problems that share the same certification-hardness status as .
In other words, either all of them admit a polynomial certificate or none of them.
Despite apparent similarities between these problems, some of the reductions require a nontrivial use of nondeterminism.


    The following parameterized problems are equivalent with respect to NPPT:
    
        
  * 
  * Knapsack[log(t+w)], Knapsack[log(p_max+w_max)]
        
  * , , 0-Sum 0-1 ILP[m]
        
        
  * Group-_q Subset Sum[log q]
    


Even though we are unable to resolve <Ref>, we believe that revealing such an equivalence class supports the claim that a polynomial certificate for is unlikely.
Otherwise, there must be some intriguing common property of all problems listed in <Ref> that has eluded researchers so far despite extensive studies in various regimes. 


Next, we present two negative results.


They constitute a proof of concept that 
can be used as a non-trivial source of hardness.


First, we adapt a reduction from <cit.> to show that scheduling with weights and due dates is hard assuming <Ref>.

[]theoremthmMainScheduling

    ≤_ppt .


It is possible to formulate this result in terms of AND-composition but we chose not to work with this framework since it is tailored for refuting kernelization and relies on concepts that do not fit into our regime (e.g., polynomial relation <cit.>).

Our second hardness result involves Group-S_k Subset Sum[k]: a variant of Subset Sum on permutation groups.
Such groups contain exponentially-large cyclic subgroups (see <Ref>) so this problem is at least as hard as Group-_q Subset Sum[log q] (which is equivalent to ).
We reduce from 3Coloring parameterized by pathwidth which is at least as hard as with respect to PPT.
Indeed, we can transform each 3SAT formula in the input (each of size (k^3)) into an instance of 3Coloring via the standard NP-hardness proof, and take the disjoint union of such instances, which implies ≤_ppt 3Coloring[pw].
Notably, the reduction in the other direction is unlikely (see <Ref>) so 
3Coloring[pw] is probably harder than .

theoremthmMainPermutation
 
    3Coloring[pw] ≤_nppt Group-S_k Subset Sum[k].


Consequently, Group-S_k Subset Sum[k]
does not admit a polynomial certificate assuming <Ref> and NP  coNP/poly.
Unlike <Ref>, this time establishing hardness requires a nondeterministic reduction.
An interesting feature of 3Coloring[pw] is that it is NL-complete under logspace reductions when
the pathwidth pw is restricted to (log n) <cit.>. 
On the other hand, Subset Sum can be solved in time (tn^2) and space polylog(tn) using algebraic techniques <cit.>.
Therefore, obtaining a logspace PPT from 3Coloring[pw] to (where pw = log n implies t = 2^polylog(n)) 
would lead to a surprising consequence: a proof that 
NL  DSPACE(polylog(n)) that is significantly different from Savitch's Theorem (see also discussion in <cit.> on low-space determinization).
This suggests that a hypothetical reduction to should either exploit the “full power” of NPPT (so it cannot be improved to a logspace PPT) or 
start directly from .



 Finally, we examine the case of the group family ^k_k on which Subset Sum is still NP-hard (as this generalizes Subset Sum on cyclic groups) 
 but enjoys a polynomial certificate.
Specifically, 
we exploit the bound on the maximal order of an element in ^k_k to prove that
 
 there always exists a solution of bounded size.

[]lemmathmZkk
    Group-^k_k Subset Sum[k] admits a polynomial certificate.


In summary, Group-G Subset Sum appears easy for G=^k_k (due to bounded maximal order), hard for G = S_k (due to non-commutativity), and the case G = _2^k lies somewhere in between. 
In the light of <Ref>, tightening this gap seems a promising avenue to settle <Ref>.



    Organization of the paper.

We begin with the preliminaries where we formally introduce the novel concepts, such as NPPT.
We prove Theorems <ref> and <ref> in Sections <ref> and <ref>, respectively.
The proofs marked with () can be found in the appendix.






§ PRELIMINARIES



We denote the set {1,…,n} by [n].
For a sequence x_1, x_2, …, x_n, its subsequence is any sequence of the form x_i_1, …, x_i_m for some choice of increasing indices 1 ≤ i_1 < … <i_m ≤ n.
All considered logarithms are binary.

A parameterized problem P is formally defined as a subset of Σ^* ×.
For the sake of disambiguation, whenever we refer to a parameterized problem, we denote the choice of the parameter in the [·] bracket, e.g., 3Coloring[pw].
We call P fixed-parameter tractable (FPT) is the containment (I,k) ∈ P can be decided in time f(k)·(|I|) for some computable function f.
We say that P admits a polynomial compression into a problem Q if there is a polynomial-time algorithm that transform (I,k) into an equivalent instance of Q of size (k).
If Q coincides with the non-parameterized version of P then such an algorithm is called a polynomial kernelization.
A polynomial Turing kernelization for P is a polynomial-time algorithm that determines if (I,k) ∈ P using an oracle that can answer if (I',k') ∈ P whenever |I'|+k' ≤(k).





    Let P Σ^* × be a parameterized problem.
    We say that P has a polynomial certificate if there is an algorithm 𝒜 that, given an instance (I,k) of P and a string y of (k) bits, runs in polynomial time and accepts or rejects (I,k) with the following guarantees.
    
        
  * If (I,k) ∈ P, then there exists y for which 𝒜 accepts.
        
  * If (I,k) ∉P, then 𝒜 rejects  (I,k) for every y.
    




    Let P Σ^* × and Q Σ^*.
    Suppose that Q ∈ NP and P admits a polynomial compression into Q.
    Then P admits a polynomial certificate.


    For a given instance (I,k) of P we execute the compression algorithm to obtain an equivalent instance I' of Q of size (k).
    Since  Q ∈ NP the instance I' can be solved in polynomial-time with an access to a string y of (|I'|) = (k) nondeterministic bits.
    Then y forms a certificate for (I,k).




    Let P,Q Σ^* × be parameterized problems.
    An algorithm 𝒜 is called a polynomial parameter transformation (PPT) from P to Q if, given an instance (I,k) of P, runs in polynomial time, and outputs an equivalent instance (I',k') of Q with k' ≤(k).

    An algorithm ℬ is called a nondeterministic polynomial parameter transformation (NPPT) from P to Q if, given an instance (I,k) of P and a string y of (k) bits, runs in polynomial time, and outputs an instance (I',k') of Q with the following guarantees.
    
        
  * k' ≤(k)
        
  * If (I,k) ∈ P, then there exists y for which ℬ outputs (I',k') ∈ Q.
        
  * If (I,k) ∉P, then ℬ outputs (I',k') ∉Q for every y.
    


Clearly, PPT is a special case of NPPT.
We write P ≤_ppt Q (P ≤_nppt Q) if there is a (nondeterministic) PPT from P to Q.
We write P ≡_ppt Q (P ≡_nppt Q) when we have reductions in both directions.
It is easy to see that the relation ≤_nppt is transitive.
Similarly as the relation ≤_ppt is monotone with respect to having a polynomial kernelization, the relation ≤_nppt
is monotone with respect to having a polynomial certificate. 


     Let P,Q ∈Σ^* × be parameterized problems. If  P ≤_nppt Q and Q admits a polynomial certificate then P does as well.


    Given an instance (I,k) of P the algorithm guesses a string y_1 of length (k) guiding the reduction to Q and constructs an instance (I',k') with k' = (k).
    Then it tries to prove that (I',k') ∈ Q by guessing a certificate y_2 of length  (k') = (k).


A different property transferred by PPT is polynomial Turing kernelization.
Hermelin et al. <cit.> proposed a hardness framework for this property by considering complexity classes closed under PPT (the WK-hierarchy).

Next, we prove the equivalence mentioned in the Introduction. 



    Suppose P Σ^* × admits an algorithm 𝒜 deciding if (I,k) ∈ P in time 2^p(k)(|I|)  where p(·) is a polynomial function. 
    Then P[k] ≡_ppt P[k+log |I|].


    The direction  P[k+log |I|] ≤_ppt 
 P[k] is trivial.
    To give a reduction in the second direction, we first check if p(k) ≤log |I|.
    If yes, we execute 𝒜 in time (|I|) and according to the outcome we return a trivial yes/no-instance.
    Otherwise we have log |I| < p(k) so we can output (I,k') for the new parameter k' = k + log |I| being polynomial in k.






    Pathwidth.

A path decomposition of a graph G is a
sequence 𝒫 = (X_1,X_2,…,X_r) of bags, where X_i  V(G), and:

    
  * For each v ∈ V(G) the set {i | v ∈ X_i} forms a non-empty subinterval of [r]. 
    
  * For each edge uv ∈ E(G) there is i ∈ [r] with {u,v}⊆ X_i.


The width of a path decomposition is defined as max_i=1^r |X_i| - 1. The pathwidth of a graph G is the minimum width of a path decomposition of G.

<cit.>

    If a graph G has pathwidth at most p, then it admits a nice path decomposition 𝒫 = (X_1,X_2,…,X_r) of width at most p, for which:

    
  * X_1 = X_r = ∅.
    
  * For each i ∈ [r-1] there is either a vertex v ∉X_i for which X_i+1 = X_i ∪{v} or a vertex v ∈ X_i for which X_i+1 = X_i {v}.

Furthermore, given any path decomposition of G, we can turn it into a nice path decomposition of no greater width, in polynomial time.



The bags of the form X_i+1 = X_i ∪{v} are called introduce bags while the ones of the form X_i+1 = X_i {v} are called forget bags.

Similarly as in the previous works <cit.> we assume that a path decomposition of certain width is provided with the input.
This is not a restrictive assumption for our model since pathwidth can be approximated within a polynomial factor in polynomial time <cit.>.





    Group theory.

The basic definitions about groups can be found in the book <cit.>.
A homomorphism between groups G,H is a mapping ϕ G → H  that preserves the group operation, i.e., ϕ(x) ∘_H ϕ(y) = ϕ(x ∘_G y) for all x,y ∈ G.
An isomorphism is a bijective homomorphism and
an automorphism of G is an isomorphism from G to G. 
We denote by Aut(G) the automorphism group of G with the group operation given as functional composition.
A subgroup N of G is normal if for every g ∈ G, n ∈ N we have g ∘_G n ∘_G g^-1∈ N.

The symmetric group S_k comprises permutations over the set [k] with the group operation given by composition.
For a permutation π∈ S_k we consider a directed graph over the vertex set [k] and arcs given as {(v,π(v)) | v ∈ [k]}.
The cycles of this graph are called the cycles of π.

We denote by _k the cyclic group with addition modulo k.

We write the corresponding group operation as ⊕_k.
An order of an element x ∈ G is the size of the cyclic subgroup of G generated by x.
The Landau's function g(k) is defined as the maximum order of an element x in S_k. It is known that g(k) equals max𝗅𝖼𝗆(k_1,…,k_ℓ) over all partitions k = k_1 + … + k_ℓ (these numbers correspond to the lengths of cycles in x) and that g(k) = 2^Θ(√(klog k)) <cit.>. 
An element of large order can be found easily if we settle for a slightly weaker bound.


    For each k there exists π∈ S_k of order 2^Ω(√(k)/log k) and it can be found in time (k).


    Consider all the primes p_1,…,p_ℓ that are smaller than √(k).
    By the prime number theorem there are ℓ = Θ(√(k)/log k) such primes <cit.>.
    We have p_1 + … + p_ℓ≤√(k)·√(k) = k so we can find a permutation in S_k with cycles of lengths p_1,…,p_ℓ (and possibly trivial cycles of length 1).
    We have 𝗅𝖼𝗆(p_1,…,p_ℓ) = ∏_i=1^ℓ p_i ≥ 2^ℓ = 2^Ω(√(k)/log k).


For two groups N, H and a homomorphism ϕ H → Aut(N) we define the outer semidirect product <cit.> N ⋊_ϕ H as follows.
The elements of N ⋊_ϕ H are {(n,h) | n ∈ N, h ∈ H} and the group operation ∘ is given as (n_1,h_1) ∘ (n_2,h_2) = n_1 ∘ϕ_h_1(n_2), h_1 ∘ h_2.
A special case of the semidirect product occurs when we combine subgroups of a common group.



Let G be a group with a normal subgroup N and a subgroup H, such that every element g ∈ G can be written uniquely 
as g = n∘ h for n ∈ N, h ∈ H.
Let ϕ H → Aut(N) be given as ϕ_h(n) = h∘ n ∘ h^-1 (this is well-defined because N is normal in G).
Then G is isomorphic to the semidirect product N ⋊_ϕ H.


Group-G Subset SumA sequence of elements g_1, g_2,…,g_n ∈ G, an element g ∈ Glog |G|Is there a subsequence (i_1 < i_2 < … < i_r) of  [n]
such that g_i_1∘ g_i_2∘…∘ g_i_r = g?

We assume that the encoding of the group elements as well as the group operation ∘ are implicit for a specific choice of a group family.
For a group family parameterized by k, like (S_k)_k=1^∞, we treat k as the parameter.
In all considered cases it holds that k ≤log |G| ≤(k) so these two parameterizations are equivalent under PPT.



§ EQUIVALENCES



We formally introduce the variants of ILP that will be studied in this section.

0-1 ILP
A matrix A ∈{-1,0,1}^m × n, a vector b ∈^m
m
Is there a vector x ∈{0,1}^n for which Ax=b?

In Monotone 0-1 ILP we restrict ourselves to matrices A ∈{0,1}^m × n.
In 0-Sum 0-1 ILP we have A ∈{-1,0,1}^m × n and we seek a binary vector x  0 for which Ax=0.

We first check that all the parameterized problems considered in this section are solvable in time 2^k^(1)n^(1).
For we can use the classic (tn)-time algorithm <cit.> which can be easily modified to solve Group-_q Subset Sum[log q] in time (qn).
For Knapsack[log(p_max + w_max)] there is an (p_max· w_max· n)-time algorithm <cit.> which also works for the larger parameterization by log(t+w).
Next, can be solved in time 2^(m^2log m)· n using the algorithm for general matrix A <cit.>.
This algorithm can be used to solve 0-sum 0-1 ILP[m] due to <Ref>.
Hence by <Ref> we can assume in our reductions that (log n) is bounded by a 
polynomial function of the parameter.




    Knapsack[log(t + w)] ≡_ppt Knapsack[log(p_max + w_max)].


    We only need to show the reduction from Knapsack[log(p_max + w_max)].
    When p_max· n < t we can afford taking all the items. 
    On the other hand, if w_max· n < w then no solution can exist.
    Therefore, we can assume that  log t ≤log p_max + log n and log w ≤log w_max + log n.
    By <Ref> we can assume log n to be polynomial in log(p_max + w_max) so the new parameter log(t + w) is polynomial in the original one.   





    ≡_nppt Knapsack[log(t + w)].


    The (≤) reduction is standard: we translate each input integer p_i into an item (p_i,p_i) and set w=t.
    Then we can pack items of total weight t into a knapsack of capacity t if and only if the Subset Sum instance is solvable.

    Now consider the (≥) reduction.
    Let k = log(t + w).
    
    
    
    By the discussion at the beginning of this section we can assume that log n ≤log(t· w) ≤ 2k.
    We can also assume that w_max < w as any item with weight exceeding w and size fitting into the knapsack would form a trivial solution.
    Let W = w · n + 1.

    Suppose there is a set of items with total size equal t' ≤ t and total weight equal w' ≥ w.
    Note that w' must be less than W.
    We nondeterministically choose t' and w': this requires guessing log t + log W ≤ 4k bits.
    Now we create an instance of Subset Sum by mapping each item (p_i, w_i) into integer p_i · W + w_i and setting the target integer to t” = t' · W + w'.
    If we guessed (t',w') correctly then such an instance clearly has a solution.
    On the other hand, if this instance of Subset Sum admits a solution then we have ∑_i ∈ I (p_i · W + w_i) =  t' · W + w' for some  I  [n]. 
    Since both w' and ∑_i ∈ I' w_i belong to [1,W) we must have ∑_i ∈ I w_i = w' and ∑_i ∈ I p_i = t' so the original instance of Knapsack has a solution as well.
    Finally, it holds that log t”≤ 5k so the parameter is being transformed linearly. 


We will need the following extension of the last argument.


    Let W ∈ and a_1,…,a_n, b_1,…,b_n be sequences satisfying a_i,b_i ∈ [0,W) for each i∈[n].
    Suppose that S := ∑_i=1^n a_i W^i-1 = ∑_i=1^n b_i W^i-1.
    Then a_i=b_i for each i∈ [n].


    Consider the remainder of S when divided by W.
    Since W divides all the terms in S for i ∈ [2,n] and a_1,b_1 ∈ [0,W) we must have a_1 = (S  W) = b_1.
    Next, consider S' = (S - a_1) / W = ∑_i=2^n a_i W^i-2 = ∑_i=2^n b_i W^i-2.
    Then a_2 = (S'  W) = b_2. This argument generalizes readily to every i ∈ [n].



    ≡_nppt .


    (≤): Consider an instance ({p_1, …, p_n}, t) of Subset Sum. Let k = ⌈log t ⌉. We can assume that all numbers p_i belong to the interval [t].
    For an integer x ∈ [t] let (x) ∈{0,1}^k denote the binary encoding of x so that x = ∑_j=1^k (x)_j · 2^j-1.
    Observe that the condition x_1 + … + x_m = t can be expressed as ∑_j=1^k ∑_i=1^m (x_i)_j· 2^j-1 = t.
    
    We nondeterministically guess a sequence b = (b_1,…,b_k)
    so that b_j equals ∑_i ∈ I(p_i)_j where I  [n] is a solution.
    This sequence must satisfy max_j=1^k b_j ≤ t, and so we need k^2 nondeterministic bits to guess b.
    We check if the sequence b satisfies ∑_j=1^k b_j · 2^j-1 = t; if no then the guess was incorrect and we return a trivial no-instance.
    Otherwise we construct an instance of Monotone 0-1 ILP[k] with a system Ax = b.
    The vector b is given as above and its length is k.
    The matrix A comprises n columns where the i-th column is (p_i).
    This system has a solution x ∈{0,1}^n if and only if there exists  I  [n] so that ∑_i ∈ I(p_i)_j = b_j for all j ∈ [k].
    This implies that ∑_i ∈ I p_i = t.
    Conversely, if such a set I  [n] exists, then there is b ∈ [t]^k
    for which Ax=b admits a boolean solution.

    (≥): Consider an instance Ax=b of .  As usual, we assume log n ≤(m).
    We can also assume that ||b||_∞≤ n as otherwise Ax=b is clearly infeasible.
    We construct an instance of Subset Sum with n items and target integer t = ∑_j=1^m b_j · (n+1)^j-1.
    Note that t ≤ m· ||b||_∞· (n+1)^m so log t ≤(m).
    For i ∈ [n] let a^i ∈{0,1}^m denote the i-th column of the matrix A.
    We define p_i = ∑_j=1^m a^i_j · (n+1)^j-1 and we claim that that instance J = ({p_1, …, p_n}, t) of Subset Sum is solavble exactly when the system Ax=b has a boolean solution.

    First, if x ∈{0,1}^m forms a solution to Ax = b then for each j∈ [m] we have ∑_i=1^n x_ia^i_j (n+1)^j-1 = b_j(n+1)^j-1 and so ∑_i=1^n x_ip_i = t.
    Hence  the set I = {i ∈ [n] | x_i = 1} encodes a solution to J.
    In the other direction, suppose that there is I  [n] for which ∑_i ∈ I p_i = t.
    Then t =  ∑_j=1^m ( ∑_i ∈ I a^i_j) · (n+1)^j-1.
    Due to  <Ref> we must have b_i = ∑_i ∈ I a^i_j for each i∈[m] and there is subset of columns of A that sums up to the vector b.
    This concludes the proof.


For the next reduction, we will utilize the lower bound on the norm of vectors in a so-called Graver basis of a matrix.
For two vectors y,x ∈^n we write y ⊲ x if for every i ∈ [n] it holds that y_ix_i ≥ 0 and |y_i| ≤ |x_i|.
A non-zero vector x ∈^n belongs to the Graver basis of A ∈^m × n if Ax = 0 and no other non-zero solution Ay=0 satisfies y ⊲ x.
In other words, x encodes a sequence of columns of A, some possibly repeated or negated, that sums to 0 and none of its nontrivial subsequences sums to 0.
The following lemma concerns the existence of vectors with a large ℓ_1-norm in a Graver basis of a certain matrix.
We state it in the matrix-column interpretation.


    For every k ∈ there is a sequence (v_1,…,v_n) of vectors from {-1,0,1}^k such that
    
        
  * n = Θ(2^k),
        
  * the vectors v_1,…,v_n sum up to 0, and
        
  * no proper non-empty subsequence of (v_1,…,v_n) sums up to 0.
    
    





    ≤_ppt .


    Consider an instance Ax = b of with A ∈{0,1}^m × n.
    We can assume that A contains 1 in every column as otherwise such a column can be discarded.
    Let v_1,…,v_ℓ∈{-1,0,1}^k be the sequence of vectors from <Ref> with ℓ≥ n and k = (log n).
    Next, we can assume that ||b||_∞≤ n ≤ℓ as otherwise there can be no solution.
    We decompose b into a sum b_1 + … + b_ℓ of vectors from {-1,0,1}^m, possibly using zero-vectors for padding.
    Now we construct a matrix A' ∈{-1,0,1}^(m+k)×(n+ℓ).
    The first n columns are given by the columns of A with 0 on the remaining k coordinates.
    The last ℓ columns are of the form (-b_i,v_i) for i ∈ [ℓ].
    See <Ref> for an illustration.
    The new parameter is m+k which is m + (log n).

    We claim that Ax = b is feasible over boolean domain if and only if A'y = 0 admits a non-zero boolean solution y.
    Consider a solution x to Ax = b.
    We define y as x concatenated with vector 1^ℓ.
    In each of the first m rows we have (A'y)_j = (Ax)_j - b_j = 0.
    In the remaining k rows we have first n zero vectors followed by the sequence  v_1,…,v_ℓ which sums up to 0 by construction.
    Hence A'y = 0 while y  0.

    Now consider the other direction and let y  0 be a solution to A'y = 0.
    Let us decompose y as a concatenation of y_1 ∈{0,1}^n and y_2 ∈{0,1}^ℓ.
    First suppose that y_2 = 0.
    Then y_1  0 and Ay_1 = 0 but this is impossible since  A ∈{0,1}^m × n and, by assumption, every column of A contains 1.
    It remains to consider the case y_2  0.
    By inspecting the last k rows of A' we infer that the non-zero indices of y_2 correspond to a non-empty subsequence of  v_1,…,v_ℓ summing up to 0.
    By construction, this is not possible for any proper  subsequence of (v_1,…,v_ℓ) so we must have y_2 = 1^ℓ.
    Hence 0 = A'y = A'y_1 + A'y_2 = A'y_1 + (-b,0) and so Ay_1 = b. This concludes the proof of the reduction.


We will now reduce from to . 
The subtlety comes from the fact that in the latter problem we accept the solution x = 0 while in the first we do not.
Observe that the reduction is easy when we can afford guessing a single column from a solution.
For a matrix A ∈^m × n and i ∈ [n] we denote by A^i ∈^m × 1 the i-th column of A and by A^-i∈^m × (n-1) the matrix obtained from A by removal of the i-th column.


    An instance Ax=0 of is solvable if and only if there is i ∈ [n]
    
     such that the instance A^-iy= -A^i of is solvable. 


Using the FPT algorithm for we obtain an FPT algorithm for 0-Sum Vector[m]. 


    0-Sum Vector[m] is solvable in time 2^(m^2log m)n^2.




    ≤_nppt .


   <Ref> enables us to solve in polynomial time when log n is large compared to m, by considering all i ∈ [n] and solving the obtained instance.
   Hence we can again assume that log n ≤(m).
    In this case, <Ref> can be interpreted as an NPPT that guesses (m) bits to identify the index i ∈ [n].



    ≤_nppt .


    We decompose the matrix A as A^+ - A^- where A^+, A^- have entries from {0,1}.
    Suppose that there exists a vector x satisfying Ax = b.
    We nondeterministically guess vectors b^+, b^- that satisfy A^+x = b^+, A^-x = b^- and we check whether b^+ - b^- = b; if no then the guess is rejected.
    This requires mlog n nondeterministic bits.
    We create an instance of with 2m constraints given as A^+y = b^+, A^-y = b^-.
    If we made a correct guess, then y=x is a solution to    
    the system above.
    On the other hand, if this system admits a solution y then Ay = A^+y - A^-y = b^+ - b^- = b so y is also a solution to the original instance.



    ≡_nppt Group-_q Subset Sum[log q].


    For the reduction (≤) consider q = nt and leave t intact.
    We can assume that each input number belongs to [1,t) hence the sum of every subset belongs to [1,q) and so there is no difference in performing addition in  or _q.

    Now we handle the reduction (≥).
    Let S be the subset of numbers that sums up to t modulo q.
    Since each item belongs to [0,q) their sum in  is bounded by nq; let us denote this value as t'.
    We nondeterministically guess t' ∈ [0, nq] and check whether t' = t  m.
    We consider an instance J of Subset Sum over  with the unchanged items and the target t'.
    We have log t' ≤log n + log q what bounds the new parameter as well as the number of necessary
    nondeterministic bits.
    If the guess was correct then J will have a solution.
    Finally, a solution to J yields a solution to the original instance because t' = t  q.


Using the presented lemmas, any two problems listed in <Ref> can be reduced to each other via NPPT.



§ PERMUTATION SUBSET SUM



This section is devoted to the proof of <Ref>.
We will use an intermediate problem involving a computational model with ℓ binary counters,
being a special case of bounded Vector Addition System with States (VASS) <cit.>.
This can be also regarded as a counterpart of the intermediate problem used for establishing XNLP-hardness, which concerns cellular automata <cit.>.

For a sequence = (f_1, …, f_n), f_i ∈{O,R} (optional/required),
we say that a subsequence of [n] is -restricted if it contains all the 
indices i with f_i = R.


We say that a sequence of vectors v_1, …, v_n ∈{-1,0,1}^ℓ forms a 0/1-run if v_1 + … + v_n = 0 and for each j ∈ [n] the partial sum v_1 + … + v_j belongs to {0,1}^ℓ.

0-1 Counter Machine
Sequences 𝒱 = (v_1, …, v_n),  v_i ∈{-1,0,1}^ℓ, and = (f_1, …, f_n),  f_i ∈{O,R}.
ℓ
Is there a subsequence (i_1 < i_2 < … < i_r) of [n] that is -restricted and such that (v_i_1,v_i_2,…,v_i_r) forms a 0/1-run?

Intuitively, a vector v_i ∈{-1,0,1}^ℓ tells which of the ℓ counters should be increased or decreased.
We must “execute” all the vector v_i for which f_i = R plus some others so that the value of each counter is always kept within {0,1}.

We give a reduction from 3Coloring[pw] to .


3ColoringAn undirected graph G and a path decomposition of G of width at most pwpwCan we color V(G) with 3 colors so that the endpoints of each edge are assigned different colors?

[]lemmalemColoring

    3Coloring[pw] ≤_ppt .


In the proof, 
we assign each vertex a label from  [pw + 1]  so that the labels in each bag are distinct. 
We introduce a counter for each pair (label, color) and whenever a vertex is introduced in a bag, we make the machine increase one of the counters corresponding to its label.
For each edge uv there is a bag containing both u,v; we then insert a suitable sequence of vectors so that running it is possible if and only if the labels of u, v have active counters in different colors.
Finally, when a vertex is forgotten we deactivate the corresponding counter.

In order to encode the operations on counters as composition of permutations, we will employ the following algebraic construction.
For q ∈ consider an automorphism ϕ_1 _q^2 →_q^2 given as ϕ_1((x,y)) = (y,x).
Clearly ϕ_1 ∘ϕ_1 is identify, so there is a homomorphism ϕ_2 → Aut(_q^2) that assigns identity to 0 ∈_2 and ϕ_1 to 1 ∈_2.
We define the group U_q as the outer semidirect product  _q^2 ⋊_ϕ_2 (see <Ref>).
That is, the elements of U_q are {((x,y),z) | x,y ∈_q, z ∈_2} and the group operation ∘ is given as 


    ((x_1,y_1),z_1) ∘ ((x_2,y_2),z_2)=
       
        ((x_1 ⊕_q x_2), (y_1 ⊕_q y_2), z_1 ⊕_2 z_2)     if  z_1 = 0
    
        ((x_1 ⊕_q y_2), (y_1 ⊕_q x_2), z_1 ⊕_2 z_2)     if  z_1 = 1.


The z-coordinate works as addition modulo 2 whereas the element z_1 governs whether we add (x_2,y_2) or (y_2,x_2) modulo q on the (x,y)-coordinates.
The neutral element is ((0,0),0).
Note that U_q is non-commutative.

For ((x,y),z) ∈ U_q we define its norm as x+y.
Consider a mapping Γ{-1,0,1}→ U_q given as Γ(-1) = ((1,0),1), Γ(0) = ((0,0),0), Γ(1) = ((0,1),1).


    Let b_1,…, b_n ∈{-1,0,1} and q > n.
    Then  b_1,…, b_n forms a 0/1-run (in dimension ℓ=1) if and only if the group product g = Γ(b_1) ∘Γ(b_2) ∘…∘Γ(b_n) in U_q is of the form g = ((0,n'),0) for some n' ∈[n]. 


    Recall that Γ(0) is the neutral element in U_q.
    Moreover, removing 0 from the sequence does not affect the property of being a 0/1-run, so we can assume that b_i  ∈{-1,1} for each i ∈ [n].
    Note that the inequality q > n is preserved by this modification.
    This inequality is only needed to ensure that the addition never overflows modulo q.

    Suppose now that b_1,…, b_n is a 0/1-run.
    Then it comprises alternating 1s and -1s: (1,-1,1,-1,…,1,-1).
    Hence the product g = Γ(b_1)  ∘…∘Γ(b_n) equals (Γ(1) ∘Γ(-1))^n/2.
    We have ((0,1),1) ∘ ((1,0),1) = ((0,2),0) and so g = ((0,n),0).

    Now suppose that b_1,…, b_n is not a 0/1-run.
    Then either ∑_i=1^n b_i = 1 or ∑_i=1^j b_i ∉{0,1} for some j ∈ [n].
    In the first scenario n is odd so g has 1 on the  z-coordinate and so it is not in the form of ((0,n'),0).
    In the second scenario there are 3 cases: (a) b_1 = -1, (b) (b_i,b_i+1) = (1,1) for some i∈[n-1], or (c) (b_i,b_i+1) = (-1,-1) for some i∈[n-1].
    
    Case (a): g = Γ(-1) ∘ h = ((1,0),1) ∘ h for some h ∈ U_q of norm ≤ n-1. 
    Then g cannot have 0 at the x-coordinate because n<q and the addition does not overflow.
    
    
    
    Case (b): Γ(1)^2 = ((0,1),1)^2 = ((0,1) ⊕_q (1,0), 1 ⊕_2 1) = ((1,1),0).
    For any h_1,h_2 ∈ U_q of total norm ≤ n-1 the product h_1 ∘ ((1,1),0) ∘ h_2 cannot have 0 at the x-coordinate.

    Case (c): Analogous to (b) because again Γ(-1)^2 = ((1,0),1)^2 =  ((1,0) ⊕_q (0,1), 1 ⊕_2 1) = ((1,1),0).


Next, we show how to embed the group U_q into a permutation group over a universe of small size.
On an intuitive level, we need to implement two features: counting modulo q on both coordinates and a mechanism to swap the coordinates.
To this end, we will partition the universe into two sets corresponding to the two coordinates.
On each of them, we will use a permutation of order q to implement counting without interacting with the other set.
Then we will employ a permutation being a bijection between the two sets, which will work as a switch.
See <Ref> for a visualization.




    For every n ∈ there exist q > n and r̂ = (log^3 n) for which there is a homomorphism χ U_q → S_r̂.


    By <Ref> we can find a permutation g of order q > n in S_r for some r = (log^3 n).
    The subgroup of S_r generated by g is isomorphic to _q.
    
    We will now consider the permutation group over the set [r] ×_2, which is isomorphic to S_2r.
    Instead of writing χ explicitly, we will identify a subgroup of S_2r isomorphic to U_q.
    
    Let π_z be the permutation given as π_z(i,j) = (i,1-j) for (i,j) ∈ [r]×_2, i.e., it switches the second coordinate.
    Let π_0 act as g on [r] × 0 and as identify on  [r] × 1.
    Analogously, let π_1 act as g on [r] × 1 and as identify on  [r] × 0.
    Let N be the subgroup of S_2r generated by π_0 and π_1; it is isomorphic to _q^2 and each element of N is of the form (π_0^x, π_1^y) for some x,y ∈_q.
    Next, let H be the subgroup generated by π_z; it is isomorphic to _2.
    Now consider a homomorphism ϕ H → Aut(N) given as conjugation  ϕ_π(g) = π∘ g ∘π^-1.
    In this special case, the semidirect product N ⋊_ϕ H is isomorphic to the subgroup of S_2r generated by the elements of N and H (<Ref>).
    On the other hand, ϕ_π_z maps (π_0^x, π_1^y) ∈ N into (π_0^y, π_1^x) so this is exactly the same construction as used when defining U_q.
    We infer that U_q is isomorphic to a subgroup of S_2r and the corresponding homomorphism is given by the mapping of the generators: χ((0,1),0) = π_0, χ((1,0),0) = π_1, χ((0,0),1) = π_z.
    

Armed with such a homomorphism, we translate <Ref> to the language of permutations.


    For every n ∈ there exists r = (log^3 n), a permutation π∈ S_r of order greater than n, and a mapping Γ{-1,0,1}→ S_r so that the following holds.
    A sequence b_1,…, b_n ∈{-1,0,1} is a 0/1-run if and only if the product Γ(b_1) ∘Γ(b_2) ∘…∘Γ(b_n) is of the form π^n' for some n' ∈ [n].


    Let χ U_q → S_r be the homomorphism from <Ref> for q > n and r = (log^3 n).
    We define Γ{-1,0,1}→ S_r
    as Γ(i) = χ(Γ(i)) using the mapping Γ from <Ref>.
    
    Since χ is a homomorphism, the condition Γ(b_1) ∘…∘Γ(b_n) = ((0,n'),0) is equivalent to Γ(b_1) ∘…∘Γ(b_n) = χ(((0,n'),0)).
    We have g = χ(((0,n'),0)) for some n' ∈ [n] if and only if g = π^n' 
    for π = χ((0,1),0).
    The order of π is q > n, as requested.


For a sequence of vectors from {0,1}^ℓ we can use a Cartesian product of ℓ permutation groups S_r to check the property of being a 0/1-run by inspecting the product of permutations from S_ℓ r. 
This enables us to encode the problem with binary counters as Group-S_k Subset Sum[k].

We remark that we need nondeterminism to guess the target permutation.
This boils down to guessing
the number n' from <Ref> for each of ℓ coordinates.

Finally, <Ref> follows by combining <Ref> with <Ref>.

[]lemmalemPermFinal

    ≤_nppt Group-S_k Subset Sum[k].






§ CONCLUSION


We have introduced the nondeterministic polynomial parameter transformation (NPPT) and used this concept to shed some light on the unresolved questions about short certificates for FPT problems.
We believe that our work will give an impetus for further systematic study of certification complexity in various contexts.


The main question remains to decipher certification complexity of .
Even though Subset Sum enjoys a seemingly simple structure, some former breakthroughs required advanced techniques such as additive combinatorics <cit.> or number theory <cit.>.
<Ref> makes it now possible to analyze through the geometric lens using concepts such as lattice cones <cit.> or Graver bases <cit.>.

Drucker et al. <cit.> suggested also to study k-Disjoint Paths and K-Cycle in their regime of polynomial witness compression.
Recall that the difference between that model and ours is that they ask for a randomized algorithm that outputs a solution.

Observe that a polynomial certificate (or witness compression) for  k-Disjoint Paths would entail an algorithm with running time 2^k^(1)n^(1) which seems currently out of reach <cit.>.
What about a certificate of size (k + log n)^(1)?

Interestingly, Planar k-Disjoint Paths does admit a polynomial certificate: if k^2 ≤log n one can execute the known 2^(k^2)n^(1)-time algorithm <cit.> and otherwise one can guess the homology class of a solution (out of n^(k)≤ 2^(k^3)) and then solve the problem in polynomial time <cit.>.
Another interesting question is whether k-Disjoint Paths admits a certificate of size (k + log n)^(1) on acyclic digraphs.
Note that we need to incorporate (log n) in the certificate size because the problem is W[1]-hard when parameterized by k <cit.>.
The problem admits an n^(k)-time algorithm based on dynamic programming <cit.>.


For K-Cycle we cannot expect to rule out a polynomial certificate via a PPT from because the problem admits a polynomial compression <cit.>, a property unlikely to hold for  <cit.>.
Is it possible to establish the 
certification hardness by NPPT (which does not preserve polynomial compression) or
would such a reduction also lead to unexpected consequences?




A different question related to bounded nondeterminism is whether 
one can rule out a logspace algorithm for 
directed reachability (which is NL-complete) using only polylog(n) nondeterministic bits.
Observe that relying on the analog of the assumption for NL would be pointless because NL = coNL by Immerman-Szelepcsényi Theorem.
This direction bears some resemblance to the question whether directed reachability can be solved in polynomial time and polylogarithmic space, i.e., whether NL  SC <cit.>.




plainurl






§ PROBLEM DEFINITIONS



Subset SumA sequence of positive integers p_1, p_2,…,p_n, integer t, all in binarylog tIs there a subsequence of  p_1, p_2,…,p_n summing up to t?

KnapsackA sequence of positive integer pairs (p_1,w_1), (p_2,w_2),…,(w_n,p_n), integers t,wlog (t+w)Is there a subset I  [n] such that ∑_i ∈ I p_i ≤ t and ∑_i ∈ I w_i ≥ w?

AND-3SATA sequence I_1, I_2, …,, I_n of instances of 3SAT, each on at most k variableskAre all the instances  I_1, I_2, …,, I_n satisfiable?




§ SCHEDULING


A job is represented by a triple (p_i,w_i,d_i) of positive integers (processing time, weight, due date).
For a sequence of n jobs a schedule is a permutation ρ [n] → [n].
The completion time C_i of the i-th job in a schedule ρ equals ∑_j ∈ [n], ρ(j) ≤ρ(i) p_j.
A job is called tardy is C_i > d_i. 
A job is being processed at time x if x ∈ (C_i - p_i, C_i].

Scheduling Weighted Tardy JobsA sequence of jobs  (p_1,w_1,d_1), (p_2,w_2,d_2),…,(w_n,p_n,d_n), integer wlog (d_max+w_max)Is there a schedule in which the total weight of tardy jobs is at most w?

We show that Scheduling Weighted Tardy Jobs does not admit a polynomial certificate as long as and <Ref> holds.
The proof utilizes a construction that appeared in a conditional lower bound on pseudo-polynomial running time for Scheduling Weighted Tardy Jobs <cit.>.
On an intuitive level, we will pack multiple instances of Subset Sum into a single instance of Scheduling Weighted Tardy Jobs and adjust the weights to enforce that all the Subset Sum instances must be solvable if a good schedule exists.

*

    Consider an instance given by a sequence of formulas Φ_1, …, Φ_n of 3SAT, each on at most k variables.
    If 2^k ≤ n then the running time 2^k·(k)· n becomes polynomial in n so we can assume that n ≤ 2^k.
    We transform each instance Φ_j into an equivalent instance (S_j,t_j) of Subset Sum following the standard NP-hardness proof for the latter <cit.>.
    The number of items in S_j, as well as logarithm of t_j, becomes linear in the number of variables plus the number of clauses  in Φ_j, which is (k^3).
    
    Now we create an instance I of Scheduling Weighted Tardy Jobs with ∑_i=1^n |S_i| items.
    Let s_j = t_1 + … + t_j for j ∈ [n] and s_0 = 0.
    For each j ∈ [n] and x ∈ S_j we create a job u with due date d_u = s_j, processing time p_u = x, and weight w_u = p_u · (n+1-j); we say that such job u comes from the j-th set.
    We claim that I admits a schedule with total weight of non-tardy jobs at least ∑_i=1^n t_i·(n+1-i) if and only if all n instances  (S_j,t_j) of Subset Sum are solvable.
    
    The implication (⇐) is easy.
    For j∈ [n] let S'_j  S_j be the subset summing up to t_j.
    We schedule first the jobs corresponding to the elements of S'_1, then the ones corresponding to S'_2, and so on.
    The tardy jobs are scheduled in the end in an arbitrary order.
    Then the jobs coming from the j-th set are being processed within the interval (s_j-1, s_j] of length t_j so they all meet their deadlines.
    The weight of the non-tardy jobs from the j-th set equals ∑_x ∈ S'_j x · (n+1-j) = t_j ·  (n+1-j) and the total weight is as promised.

    Now we prove the implication (⇒).
    Consider some schedule of jobs in the instance I with total weight of the non-tardy jobs at least ∑_i=1^n t_i·(n+1-i).
    We define two sequences (a_i), (b_i) of length s_n.
    We set a_i = (n+1-j) where j ∈ [n] is the unique index satisfying i ∈ (s_j-1, s_j].
    If there is a job u being processed at time i we set b_i = w_u/p_u, otherwise we set b_i = 0.
    We claim that for each i ∈ [s_n] it holds that b_i ≤ a_i.
    Indeed, when i ∈ (s_j-1, s_j] then any non-tardy job u processed at time i must have its due date at s_j or later.
    Hence u comes from the j'-th set, where j' ≥ j, so b_i = w_u/p_u = n+1-j' ≤ n+1-j = a_i.
    Now observe that ∑_i=1^t a_i =  ∑_j=1^n t_j·(n+1-j) whereas ∑_i=1^t b_i equals the total weight of the non-tardy jobs in the considered schedule.
    By assumption, we must have ∑_i=1^t a_i = ∑_i=1^t b_i and so a_i = b_i for all i ∈ [t].
    Therefore, for each j ∈ [n] and  i ∈ (s_j-1, s_j] we have b_i = (n+1-j) so the total processing time of the non-tardy jobs coming from the j-set equals t_j.
    Hence each instance (S_j,t_j) of Subset Sum admits a solution.

    It remains to check that the parameter log (d_max + w_max) is polynomially bounded in k.
    The maximum due date d_max equals s_n ≤ n · 2^(k^3).
    The maximum weight w_max is bounded by n times the maximum size of an element in ⋃_i=1^n S_i which is 2^(k^3).
    By the initial assumption n ≤ 2^k so  log (d_max + w_max) ≤(k).
    This concludes the proof.   





§ PERMUTATION SUBSET SUM: MISSING PROOFS



*

    Let k = pw + 1.
    By <Ref> we can assume that the given path decomposition of the graph G is nice.
    We can turn it into a sequence C of commands of the form (v), (v), (u,v) such that (i) each vertex v is introduced once and forgotten once afterwards, and (ii) for each edge uv ∈ E(G) the command (u,v) appears at some point when u,v are present (i.e., after introduction and before being forgotten). 
    Next, we assign each vertex a label from [k] in such a way that no two vertices of the same label share a bag.
    To this end, we scan the sequence C, store the current bag, and assign the colors greedily.
    Whenever we see a command (v) then the current bag must contain less than k vertices so there is some label not being used in the current bag.
    We then assign this label to v and continue.

    We will now assume that the arguments of the commands  , , refer to labels, e.g., (x) means that a vertex with label x appears in the current bag and (x,y) means that the vertices labeled x,y in the current bag are connected by an edge.

    Let D  [3]^2 be the set of all 6 ordered pairs different colors.
    For each label x ∈ [k] and each color c ∈ [3] we create a counter called x_c.
    The intended meaning if x_c = 1 is that the vertex labeled x in the current bag is assigned color c.
    We also create special counters: one named S 
    and 6 counters Z_c,d for each (c,d) ∈ D.
    
    Hence the total number of counters is ℓ = 3k + 7.

    We translate the sequence C into sequences 𝒱,  forming the instance of .
    Instead of specifying  directly, we will indicate which vectors in 𝒱 are optional and which are required.
    To concisely describe a vector in which, e.g., counter y_1 is being increased, counter y_2 is being decreased, and the remaining ones stay intact, we write
    [y_1↑,  y_2↓]. 
    We scan the sequence C and for each command we output a block of vectors, according to the following instructions.
    

    
        
  (x): We insert optional vectors [x_1↑,  S↑], [x_2↑,  S↑], [x_3↑,  S↑], followed by a required vector [S↓].
        
        Since the counter S cannot exceed 1, at most one of the first three vectors can be used.
        In the end we are required to decrease S so if we began with S set to 0 then exactly one of x_1, x_2, x_3 must be set to 1.

        
  (x): We insert optional vectors [x_1↓,  S↑], [x_2↓,  S↑], [x_3↓,  S↑], followed by a required vector [S↓].

        Similarly as before, we can decrease at most one of the counters x_1, x_2, x_3 and we will check that exactly one this events must happen.
        
        
  (x,y): 
        We insert 6 optional vectors [x_c↓,  y_d↓,  Z_c,d↑,  S↑], one for each (c,d) ∈ D.
        This is followed by required vectors [S↓], [S↑].
        Then we insert 6 optional vectors [x_c↑,  y_d↑,  Z_c,d↓,  S↓], for each (c,d) ∈ D, this time followed by [S↑], [S↓].

        Suppose that initially S is set to 0.
        The required vectors manipulating S enforce that exactly one of the first 6 vectors and exactly one of the last 6 vectors are used.
        This verifies that the vertices labeled x,y are colored with different colors. 
    


If the graph is 3-colorable then there exists a subsequence of 𝒱 whose indices are -restricted and which forms a 0/1-run.


    We will maintain the following invariant: between the blocks (1) all the special counters are set to 0, (2) for each vertex in the current bag with label x and color c the counter x_c is set to 1.
    
    When a vertex with label x and color c is introduced we choose the optional vector [x_c↑,  S↑] and subsequently S gets decreased.
    When a vertex with label x and color c is forgotten we know that x_c is currently set to 1 so we can choose the optional vector [x_c↓,  S↑] and then again S gets decreased.
    When the command (x,y) is processed we know that there is a pair (c,d) ∈ D so the counters x_c, y_d are set to 1.
    Therefore we can execute the sequence [x_c↓,  y_d↓,  Z_c,d↑,  S↑], [S↓], [S↑], [x_c↑,  y_d↑,  Z_c,d↓,  S↓], [S↑], [S↓], maintaining the invariant in the end.
    Finally, when a vertex labeled x with color c is being forgotten then the counter x_c is decreased so in the end all the counters are 0.



If there exists a subsequence of 𝒱 whose indices are -restricted and which forms a 0/1-run, then the graph is 3-colorable.


We will prove two invariants about the states of counters between the blocks: (1) all the special counters are set to 0, (2) for each x ∈ [k] if the vertex labeled x is present in the current bag then there is exactly one c ∈ [3] so that x_c is set to 1, and if there is no vertex labeled x in the current bag then all x_1,x_2,x_3 are set to 0.

We first prove (1).
Observe that each block ends with required [S↓] so it remains to analyze the counters Z_c,d.
They can be activated only in a block corresponding to command (x,y).
The required actions on S enforce that that exactly one of the first 6 optional vectors and exactly one of the last 6 optional vectors are used.
Since each vector in second group decreases some counter Z_c,d and the first group can increase only one, these two vectors must process the same pair (c,d) ∈ D.
Hence in the end all the special counters are again deactivated.

We move on to invariant (2).
First consider a command (x). Due to the initial preprocessing, no other vertex labeled x can be present in the current bag so the  counters  x_1,x_2,x_3 are inactive. 
We must activate exactly one of the counters x_1,x_2,x_3 so the invariant is preserved. An analogous argument applies to (x).
Now consider the block corresponding to command (x,y).
By the argument from the the analysis of invariant (1), the two optional vectors used in this block process the same pair (c,d) ∈ D.
So the state of  all the counters after processing this block is the same as directly before it. 

We define the 3-coloring of the graph as follows.
When a vertex v with label x is being introduced, we know that one counter x_c for some c ∈ [3] gets increased.
We assign the color c to v.
To check that this is a correct coloring, consider an edge uv.
Let x,y be the labels of u,v. 
There is a command (x,y) in C being executed when both u,v are present in the current bag.
By the analysis above, we must take one of the vectors [x_c↓,  y_d↓,  Z_c,d↑,  S↑] at the beginning of the corresponding block, which implies that the counters x_c and y_d were active at the beginning of the block.
But (c,d) ∈ D so c d and we infer that u,v must have been assigned different colors.

This concludes the correctness proof of the reduction.  





*

    Consider an instance of given by the sequences 𝒱 = (v_1, …, v_n), v_i ∈{-1,0,1}^ℓ, and = (f_1, …, f_n), f_i ∈{O,R}.
    The problem can be easily solved in time (2^ℓ· n) so we can assume from now on that log n ≤ℓ.
    Let r = (log^3 n), π∈ S_r, and Γ{-1,0,1}→ S_r be as in <Ref>.

    
    For each i ∈ [n] we construct an (ℓ+1)-tuple of permutations (p^1_i, p^2_i, …, p^ℓ+1_i) from S_r as follows.
    For each j ∈ [ℓ] we set p^j_i = Γ(v_i^j) where v_i = (v_i^1,…, v_i^ℓ).
    We set p^ℓ+1_i = π if f_i = R (i.e., the i-th vector is required) and otherwise we set p^ℓ+1_i to the identify permutation.
    Let f_C denote the number of indices with f_i = R.
    Next, let I = (i_1 < … < i_m) denote a subsequence of [n].
    We claim that the following conditions are equivalent.
    
        
  * The subsequence I is -restricted.
        
        
  * The subsequence of p^ℓ+1_1,…, p^ℓ+1_n given by indices I yields product π^f_C.
    
    To see this, observe that π has order larger than n (as guaranteed by <Ref>) so the product  π^f_C is obtained exactly when I contains all f_C indices for which f_i = R.

    We move on to the next equivalence.
    
        
  * The subsequence of v_1, …, v_n given by indices I forms a 0/1-run.
        
  * For each j ∈ [ℓ] the subsequence of p^j_1,…, p^j_n given by indices I yields product π^n_i for some n_i ∈ [n].
    
    A sequence of ℓ-dimensional vectors forms a 0/1-run if and only if each single-dimensional sequence (corresponding to one of ℓ coordinates) forms a 0/1-run.
    Fix j ∈ [ℓ].
    By <Ref> the subsequence of v^j_1, …, v^j_n given by indices I forms a 0/1-run if only only if multiplying their images under the mapping Γ yields a product of the form π^n_i for some n_i ∈ [n].
    This justifies the second equivalence.

    To create an instance of Group-S_k Subset Sum[k] we take k = (ℓ +1)· r so we can simulate multiplication in S_r^ℓ+1 by dividing [k] into (ℓ+1) subsets of size r.
    We have k = (ℓ^4) so indeed the new parameter is polynomial in ℓ.
    
    For each i ∈ [n] we transform the tuple (p^1_i, p^2_i, …, p^ℓ+1_i) into p_i ∈ S_k using the aforementioned natural homomorphism.
    We nondeterministically guess the numbers n_1,…, n_ℓ∈ [n] 
    and set the target permutation p_T as the image of (π^n_1, π^n_2, …, π^n_ℓ, π^f_C) under the natural homomorphism.
    This requires guessing ℓ·log n ≤ℓ^2 bits.   
    By the equivalences above, the instance of is solvable if and only there is a tuple (n_1,…, n_ℓ) for which the constructed instance ((p_1,…,p_n), p_T) of Group-S_k Subset Sum[k] is solvable.
    This concludes the proof.




§ REMAINING PROOFS



First, we show that Group-G Subset Sum becomes easy for the group family _k^k.
To this end, we need the following result from the 0-sum theory (see <cit.> for a survey).




    Let G be a finite commutative group, m be the maximal order of an element in G, and s satisfy s>m(1 + log(|G| / m)).
    Then any sequence a_1 …, a_s of elements in G has a non-empty subsequence that sums to zero. 


*

    We apply <Ref> to the group G = _k^k.
    The maximal order m in G is k and so we can set s = k^2log k.
    Consider an instance of Group-_k^k Subset Sum[k] and a solution a_1 + … + a_ℓ = t that minimizes ℓ.
    If ℓ≥  s then there exists a non-empty subsequence of a_1, …, a_ℓ that sums to 0.
    Removing this subsequence from  a_1, …, a_ℓ does not modify the sum so we obtain a shorter solution, which yields a contradiction.
    Hence ℓ < s and so we can guess the solution using ℓ· (klog k) = k^3log^2 k bits.


Next, we prove that becomes easy when we drop the restriction that each element can be used by a solution only once.
Recall that in Unbounded Subset Sum we ask for a multiset of integers from {p_1, p_2,…,p_n} that sums up to t.
In fact, in this variant there always exists a solution with small support.
This is a special case of the integer version of Carathéodory's theorem <cit.>.


    Unbounded Subset Sum[log t] admits a polynomial certificate.


    A solution can be represented as a multiset of input integers.
    Consider a solution S that minimizes the number ℓ of distinct integers.
    Suppose for the sake of contradiction that ℓ > log t and let S_D denote the set of distinct elements in S.
    There are 2^ℓ > t subsets of S_D and each of them has a sum in the interval [0,t].
    Consequently, there are two subsets S_1, S_2  S_D that give the same sum.
    The same holds for S_1  (S_1 ∩ S_2) and S_2  (S_1 ∩ S_2) so we can assume that S_1,S_2 are disjoint.
    Let x ∈ S_1 ∪ S_2 be an element with the least multiplicity in S; let m denote this multiplicity and assume w.l.o.g. that x ∈ S_1.
    We construct a new solution S' from S: we decrease the multiplicity of each element from S_1 by m and increase multiplicity of each element from S_2 by m.
    By the choice of m, the multiplicity of x drops to 0 and we never decrease the multiplicity of any element below 0.
    Therefore, S' is also a valid solution with a lower number of distinct elements; a contradiction.

    We have shown that ℓ≤log t.
    Moreover, the multiplicity of each element in S cannot exceed t.
    We can guess this solution by guessing the set S_D and the numbers from [t] representing their multiplicities, using log^2 t nondeterministic bits.



    Binary (k,Δ)-ILP admits a Levin certificate of size (k+Δ).



Finally, we justify why we should not expect a PPT from 3-Coloring[pw] to .
In fact, our argument works already for parameterization by treedepth.
We consider the standard CNF-SAT problem with unbounded arity parameterized by the number of variables
 n.
It is known that CNF-SAT[n]  is MK[2]-hard <cit.> and as such it is considered unlikely to admit a polynomial Turing kernelization.
On the other hand, admits a trivial polynomial Turing kernelization
and so it suffices to show a PPT from CNF-SAT[n] to 3-Coloring[pw].
An analogous hardness has been observed for Indepedent Set parameterized by treewidth <cit.>.


    CNF-SAT[n] ≤_ppt 3-Coloring[pw]. Consequently, 3-Coloring[pw] is MK[2]-hard.


    
    We adapt the known NP-hardness proof of 3-Coloring and we refer to the 3 colors as T (true), F (false), B (blocked).
    Let g_B, g_F be two special vertices, connected by an edge, and let B, F refer to the colors used by g_B, g_F respectively.
    
    We will utilize the 2-OR-gadget that, for given vertices u,v, uses a fresh vertex g_uv (the output), so that (i) u,v must be colored with T or F,
    (ii) the color of g_uv must be F if both u,v have color F,
    (iii) the vertex g_uv can be colored with T if  one of u,v has color T.
    
    First, connect both u,v to g_B to ensure (i).
    Next, create auxiliary vertices u',v' and edges uu', vv', u'v'.
    The vertex g_uv is connected to u',v',g_B.
    Suppose that both u,v have color F.
    Then the colors used by u',v' must be {T,B} and the only color left for g_uv is F.
    Next, if one of u,v has color T then  u',v' can be colored with {F,B} and g_uv can use T.

    We can use the output of the 2-OR-gadget as an input of the next gadget and so for each d ∈ we can construct a d-OR-gadget that takes d vertices, uses (d) auxiliary vertices, and its output implements the OR-function of the input colors.

    We are now in position to give the reduction from CNF-SAT[n].
    For each variable x_i we create vertices x_i^Y, x_i^N, corresponding to literals x_i,  x_i, and connect them to the special vertex g_B.
    For each clause ϕ with arity d we create a d-OR-gadget over the vertices corresponding to its literals, and connect its output to the special vertex g_F.
    First, we analyze the pathwidth of such a graph G by constructing a path decomposition.
    We put all the literal and special vertices (2n+2 in total) in all the bags.
    Then each bag corresponds to some clause and contains the respective OR-gadget on (n) vertices.
    Consequently, we obtain a path decomposition of G of width (n).

    Suppose now that the given instance from CNF-SAT[n] admits a satisfying assignment.
    If the variable x_i is set to True, we color x_i^Y with T and x_i^N with F.
    Otherwise we use the opposite coloring.
    By the property (iii) of the OR-gadget, there is a coloring that assigns T to each output of the gadget and so we obtain a proper 3-coloring.

    In the other direction, consider a proper 3-coloring of G.
    Let B,F be the colors used by g_B,g_F.
    Each pair (x_i^Y,x_i^N) is colored as T/F or F/T; we treat x_i as set to True when x_i^Y uses color T.
    The output of each OR-gadget must utilize the color unused by g_B,g_F, that is, T.
    By the property (ii) of the OR-gadget, one of the inputs also must be colored with T.
    Hence the described truth-assignment satisfies every clause. 


