On Strong NP-Completeness of Rational Problems
Dominik Wojtczak









University of Liverpool, UK





On Strong NP-Completeness of Rational Problems
    Dominik Wojtczak
    Received xxxx; accepted xxxx
==============================================






The computational complexity of 
the partition, 0-1 subset sum, unbounded subset sum, 0-1 knapsack and unbounded knapsack problems 
and their multiple variants
were studied in numerous papers in the past 
where all the weights and profits were assumed to be integers.


We re-examine here the computational complexity of all these problems
in the setting where the weights and profits are allowed 
to be any rational numbers. 
We show that all of these problems in this setting become 
strongly NP-complete and, as a result,
no pseudo-polynomial algorithm can exist for solving them
unless =. Despite this result we show that 
they all still admit a fully polynomial-time approximation scheme.
















§ INTRODUCTION




The problem of partitioning a given set of items into two parts with equal total weights (that we will refer to as ) 
goes back at least to 1897 <cit.>.
A well-known generalisation is the problem of finding a subset with a given total weight (0-1 ) and
the same problem where each item can be picked more than once ().
Finally, these are commonly generalised to the setting where each item also has a profit and
the aim is to pick a subset of items with the total profit higher than a given threshold, 
but at the same time their total weight smaller than a given capacity (0-1 ).
A variant of the last problem where each item can be picked more than once is also studied ().

The problem has numerous applications: its solutions can be used for designing better lower bounds for scheduling problems (see, e.g., <cit.> and <cit.>) and it appears as a subproblem in numerous combinatorial problems (see, e.g., <cit.>). At the same time, many industrial problems can be formulated as knapsack problems: cargo loading, cutting stock, 
capital budgeting, portfolio selection, interbank clearing systems, knapsack cryptosystems, and combinatorial auctions 
to name a couple of examples (see Chapter 15 in <cit.> for more details regarding these problems and their solutions).

The decision problems studied in this paper were among the first ones to be shown to be NP-complete <cit.>. 
At the same they are considered to be the easiest problems in this class, 
because they are polynomial time solvable if items' weights and profits are represented using the unary notation
(in other words, they are only weakly NP-complete). 
In particular, they can be solved in polynomial time when these numbers are bounded by a fixed constant
(and the number of items is unbounded).
Furthermore, the optimisation version of all these decision problems admit fully polynomial-time approximation schemes (FPTAS), i.e.,
we can find a solution with a value at least equal to (1 - ϵ) times the optimal in time polynomial in the size of the input and 1/ϵ for any ϵ > 0.

To the best of our knowledge, the computational complexity analysis of all these problems was only studied so far 
under the simplifying assumption that all the input values are integers.
However, in most settings where these problems are used, these numbers are likely to be given as rational numbers instead.
We were surprised to discover that the computational complexity in such a rational setting was not properly studied before.
Indeed, as pointed out in <cit.>:

	A rather subtle point is the question of rational coefficients. 
	Indeed, most textbooks get rid of this case, where some or all input values are non-integer, 
	by the trivial statement that multiplying with a suitable factor, 
	e.g. with the smallest common multiple of the denominators, 
	if the values are given as fractions or by a suitable power of 10, 
	transforms the data into integers.
	Clearly, this may transform even a problem of moderate size into a rather unpleasant problem with huge coefficients.

This clearly looks like a fundamental gap in the understanding of the complexity of these computational problems.
Allowing the input values to be rational makes a lot of sense in many settings.

For example, we encountered this problem when studying an optimal control in multi-mode systems with discrete costs <cit.>
and looking at the weighted voting games (see, e.g., <cit.> where the weights are defined to be rational).

An interesting real-life problem is checking whether we have the exact amount when paying, which is important in a situation when no change can be given.
While we take decimal monetary systems for granted these days, there were plenty of non-decimal monetary systems in use not so long ago.
For example, in the UK between 1717 and 1816 one pound sterling was worth twenty shillings, one shilling was worth twelve pence, and one guinea was worth twenty one shillings.












We show here that allowing the input numbers to be rational makes a significant difference and in fact all these decision problems in such a setting become strongly -complete <cit.>, i.e., they are -complete even when all their numerical values are at most polynomial
in the size of the rest of the input or, equivalently, if all these numerical values are represented in unary.
To prove this we will show an -completeness of a new variant of the satisfiability problem and
use results regarding distribution of prime numbers.
As a direct consequence of our result, there does not exist any pseudo-polynomial algorithms for solving these decision problems unless =.
At the same time, we will show that they still all admit a fully polynomial-time approximation scheme (see, e.g., <cit.>).
This may seem wrong, because the paper that introduced strong -completeness 
<cit.> also showed that

no strongly -hard problem can admit an FPTAS unless =. 
However, the crucial assumption made there is that the objective function is integer valued,
which does not hold in our case.









Related work. 

The decision problems studied in this paper are so commonly used that they have already been thousands of papers published
about them and many of their variants, including multiple algorithms and heuristic for solving them precisely and approximately.
There are also two full-length books, <cit.> and <cit.>, solely dedicated to these problems. 

Several extensions of the classic knapsack problem were shown to be strongly NP-complete.
These include partially ordered knapsack <cit.> (where we need to pick a set of items closed under predecessor), graph partitioning <cit.> (where we need to partition a graph into m disjoint subgraphs under cost constraints),
multiple knapsack problem <cit.>, knapsack problem with conflict graphs <cit.> (where we restrict which pairs of items can be picked together), and quadratic knapsack problem <cit.> 
(where the profit of packing an item depends on how well it fits together with the other selected items).

The first FPTAS for the optimisation version of the problem was established in 1975 by Ibarra and Kim <cit.> 
and independently by Babat <cit.>. Multiple other, more efficient, FPTAS for these problems followed (see, e.g., <cit.>).

Plan of the paper.

In the next section, we introduce all the used notation as well as formally define all the decision problems that we study in this paper.
In Section <ref>, we analyse the amount of space one needs to write down the first n primes in the unary notation
as well as a unique representation theorem concerning sums of rational numbers.
In Section <ref>, we define a couple of new variants of the well-known satisfiability problem for Boolean formulae in 3-CNF form
and show them to be -complete.
Our main result, concerning the strong NP-hardness of all the decision problems studied in this paper 
with rational inputs, can be found in Section <ref> 
and it builds on the results from Sections <ref> and <ref>.
We briefly discuss the existence of FPTAS for the optimisation version of our decision problems in Section <ref>.
Finally, we conclude in Section <ref>.



§ BACKGROUND



Let _≥ 0 be the set of non-negative rational numbers.
We assume that a non-negative rational number is represented as usual as
a pair of its numerator and denominator, 
both of which are natural numbers that do not have a common divisor greater than 1. 
A unary representation of a rational number is simply a pair of its numerator and denominator represented in unary.
For two natural numbers a and n, let a  n ∈{0,…,n-1} 
denote the remainder of dividing a by n.
For any two numbers a,b ∈{1,…,n}, 
we define their addition modulo n, denoted by ⊕_n, as follows:
a ⊕_n b = ((a + b - 1)  n) + 1.
Note that we subtract and add 1 in this expression so that
the result of this operation belongs to {1,…,n}.
Similarly we define the subtraction modulo n, denoted by ⊖_n, as follows:
a ⊖_n b = ((n + a - b - 1)  n) + 1.
We assume that ⊕_n and ⊖_n operators have higher precedence
than the usual + and - operators.











We now formally define all the decision problems that we study in this paper.


	Assume we are given a list of n items with rational non-negative weights A = {w_1, …, w_n} 
	and a target total weight W ∈_≥ 0. 
	
	0-1 : 
	Does there exists a subset B of A such that 
	the total weight of B is equal to W?
	
	:
	Does there exist a list of non-negative integer quantities 
	(q_1, …, q_n) such that 
	
    ∑_i=1^n q_i · w_i = W ?

	(Intuitively, q_i denotes the number of times the i-th item in A is chosen.)


A natural generalisation of this problem where each item gives us a profit when picked
is the well-known knapsack problem.


	Assume there are n items whose non-negative rational weights and profits are given
	as a list L = {(w_1,v_1), …, (w_n,v_n)}.
	Let the capacity be W ∈_≥ 0 and the profit threshold be V ∈_≥ 0.
	
	0-1 : 
	Is there a subset of L whose
	total weight does not exceed W
	and total profit is at least V?	
	
	:
	Is there a list of non-negative integers
	(q_1, …, q_n) such that 
	
    ∑_i=1^n q_i · w_i ≤ W      and     ∑_i=1^n q_i · v_i ≥ V?
 
	(Intuitively, q_i denotes the number of times the i-th item in A is chosen.)
	


Finally, a special case of the problem is the problem.


	Assume we are given a list of n items with non-negative rational weights A = {w_1, …, w_n}.
	
	Can the set A be partitioned into two sets with equal total weights?
	


Now let us compare the size of a problem instance when represented in binary and unary notation.
Let A = {w_1, …, w_n} be an instance such that w_i = a_i/b_i where a_i, b_i ∈ℕ for all i=1,…,n.
Notice that the size of A is Θ(∑_i=1^n log(a_i) + ∑_i=1^nlog(b_i)) when written down in binary 
and Θ(∑_i=1^n a_i + ∑_i=1^n b_i) in unary. 
If we now multiply all weights in A by ∏_i=1^n b_i then we would 
get an equivalent instance A' with only integer weights. 
The size of A' would be 
Θ(∑_i=1^n log(a_i/b_i∏_j=1^n b_j)) = Θ(∑_i=1^n log a_i + (n-1)∑_i=1^n log b_i) 
when written down in binary and in unary: Θ(∑_i=1^n (a_i/b_i∏_j=1^n b_j)) = Ω(min a_i · (min b_i)^n-1). Notice that the first expression is polynomial in the size of the original instance while the second one
may grow exponentially. A similar analysis shows the same behaviour for all the other decision problems studied in this paper.



§ PRIME SUSPECTS



In this section we first show that writing down all the first n prime numbers in the unary notation can be done
using space polynomial in n. Let π_i denote the i-th prime number. The following upper bound is known for π_i.


	
	
    π_i < i(log i + loglog i)     for     i ≥ 6



This estimate gives us the following corollary that will be used in the main result of this paper.


	
	The total size of the first n prime numbers, when written down in unary, is (n^2log n).
	Furthermore, they can be computed in polynomial time.


	Let n ≥ 6, because otherwise the problem is trivial.
	Thanks to Theorem <ref>, it suffices to list all natural numbers smaller than 2nlog n
	(because n(log n + loglog n) ≤ 2nlog n)
	and use the sieve of Eratosthenes to remove all nonprime numbers from this list.
	It follows that writing down the first n prime numbers requires (n^2log n) space.
	The sieve can easily be implemented in polynomial time and, to be precise,
	in this case (n^2log^2 n) additions and (nlog n) bits of memory would suffice.


Now we prove a result regarding a unique representation of rational numbers expressed as sums of fractions with prime denominators, which in a way is quite similar to the Chinese remainder theorem.








	
	Let (p_1, …, p_n) be a list of n different prime numbers.
	Let	(a_0,a_1, …, a_n) and (a_0,b_1,…,b_n) 
	be two lists of integers such that
	|a_i - b_i| < p_i holds for all i = 1,…,n. 
	We then have
	
    a_0 + a_1/p_1 + … + a_n/p_n = b_0 + b_1/p_1 + … + b_n/p_n

	
    if and only if
 
	
    a_i = b_i   for all   i = 0,…,n.



	(⇐)
	If a_i = b_i  for all  i = 0,…,n holds then obviously
	
    a_0 + a_1/p_1 + … + a_n/p_n = b_0 + b_1/p_1 + … + b_n/p_n.

	
	(⇒)
	We need to consider two cases: a_0 = b_0 and a_0 ≠ b_0. 
	In the first case, suppose that
	a_j ≠ b_j for some j ∈{1,…,n}. If we multiply
	
    a_1-b_1/p_1 + … + a_n-b_n/p_n   by   ∏_i=1^n p_i
 then we would get an integer, which is not divisible by p_j 
	(because 0 < |a_j-b_j| < p_j)
	and so this expression cannot be equal to 0.
	Therefore, in this case, 
	
    a_0 + a_1/p_1 + … + a_n/p_n≠ b_0 + b_1/p_1 + … + b_n/p_n.

	In the second case, if a_i = b_i  for all  i = 1,…,n holds
	then clearly 
	
    a_0 + a_1/p_1 + … + a_n/p_n≠ b_0 + b_1/p_1 + … + b_n/p_n.

	Otherwise, again suppose that
	a_j ≠ b_j for some j ∈{1,…,n}.
	If we multiply
	
    a_0 - b_0 + a_1-b_1/p_1 + … + a_n-b_n/p_n   by   ∏_i=1^n p_i
 then we would get an integer, which is not divisible by p_j 
	(because 0 < |a_j-b_j| < p_j)
	and so this expression cannot be equal to 0.
	Therefore, again, in this case, 
	
    a_0 + a_1/p_1 + … + a_n/p_n≠ b_0 + b_1/p_1 + … + b_n/p_n.





§ IN THE PURSUIT OF SATISFACTION



The Boolean satisfiability () problem for formulae 
was the first problem to be shown -complete by Cook <cit.>
and Levin <cit.>.
Karp <cit.> showed that is also NP-complete for
formulae in the conjunctive normal form where each clause has at most three literals.
Of course, the same holds for formulae with exactly three literals in each clause.
This is simply because we can introduce a new fresh variable for every missing literal in each clause 
of the given formula without changing its satisfiability.
The set of all formulae with exactly three literals in each clause will denoted by 3-CNF.
Tovey <cit.> showed that is also NP-complete for 
3-CNF formulae in which each variable occurs at most 4 times.
We will denote the set of all such formulae by .
Schaefer defined in <cit.> the problem for 3-CNF formulae 

in which one asks for an truth assignment that makes exactly one literal in each clause true,
and showed it to be -complete.
We define here a new problem for 3-CNF formulae, which 
asks for a valuation that makes exactly the same number of literals
true in every clause (this may be zero, i.e., such a valuation may not make the formula true).
This problem will be a crucial ingredient in the proof of the main result of this paper.

The first step is to show that problem is -complete even when restricted to formulae.


	
	The problem for is -complete.


	Obviously the problem is in , because we can simply guess a valuation 
	and check how many literals are true in each clause in linear time.
	
	To prove -hardness, we are going to reduce from the problem for , 
	which is NP-complete <cit.>.
	Assume we are given a formula
	
	
    ϕ = C_1 ∧ C_2 ∧…∧ C_m

	with m clauses C_1, …, C_m and n propositional variables v_1, …, v_n,
	where C_j = x_j ∨ y_j ∨ z_j for j = 1,…,m and
	each x_j,y_j,z_j is a literal equal to v_i or ¬ v_i
	for some i.
	We will construct a formula ϕ' with 3m clauses and n + 4m propositional variables 
	such that ϕ is satisfiable iff ϕ' is an instance of the problem.
	This will be based on the construction already given in <cit.>.
	
	The formula ϕ' is constructed by replacing each clause in ϕ with three new clauses.
	Specifically, the j-th clause C_j = x_j ∨ y_j ∨ z_j is replaced by
	C'_j := (¬ x_j ∨ a_j ∨ b_j) ∧ (b_j ∨ y_j ∨ c_j) ∧ (c_j ∨ d_j ∨¬ z_j)
	where a_j, b_j, c_j, d_j are four fresh propositional variables.
	It is quite straightforward to check that only a valuation that makes C_j true 
	can be extended to a valuation that makes exactly one literal true in each of the clauses in C'_j.
	Notice that such a constructed ϕ' is a formula, because this transformation does not 
	increase the number of occurrences of any of the original variables in ϕ
	and each of the new variables is used at most twice.
	
	Now, if there exists a valuation that makes every clause in ϕ true, then as argued above it can be extended to a valuation 
    that makes exactly one literal true in every clause in ϕ'.
	
	To show the other direction, let ν be a valuation that makes exactly one literal true in every clause in ϕ'.
	Consider for every j = 1,…,m the projection of ν on the set of variables
	occurring in the clause C_j. Suppose that such a valuation makes C_j false.
    It follows that it would not be possible to extend this valuation 
    to a valuation that makes exactly one literal true in every clause in C'_j. 
    However, we already know that ν is such a valuation, so this leads to a contradiction.


Although Theorem <ref> is of independent interest, all that we need it for is to prove our next theorem. 


    
	The problem for   formulae is -complete.


	The problem is clearly in , because we can simply guess
	a valuation and check whether it makes exactly the same number of literals
	in every clause true.
	
	To proof -hardness, we reduce from the problem for formulae (Theorem <ref>). 
	Let ϕ be any formula and let us consider a new formula 
	ϕ' = ϕ∧ (x ∨ x ∨¬ x),
	where x is a fresh variable that does not occur in ϕ.
	Notice that ϕ' is also a formula.
	We claim that ϕ is an instance of iff ϕ' is an instance of .
	
	(⇒) 
	If ν is a valuation that makes exactly one literal in every clause in ϕ true, 
	then extending it by setting ν'(x) = would
	make exactly one literal in every clause in ϕ' true.
	
	(⇐) 
	Let ν be a valuation that makes the same number of literals in every clause in ϕ' true.
	This number cannot possibly be 0 or 3, 
	because there is at least one true literal and one false literal in 
	the clause (x ∨ x ∨¬ x).
	
	If ν makes exactly one literal in every clause in ϕ' true, then 
	the same holds for ϕ.
	
	If ν makes exactly two literals in every clause true, then 
	consider the valuation ν' such that ν'(y) = ¬ν(y) for every propositional variable y in ϕ'.
	Notice that ν' makes exactly one literal in every clause in ϕ' true,
	so the same holds for ϕ. 	































































































§ BEING RATIONAL MAKES YOU STRONGER



In this section, we build on the results obtained in the previous two section and show
strong NP-hardness of all the decision problems defined in Section <ref>.
As a direct consequence, no pseudo-polynomial algorithm can exist for solving any of these
problems unless =.
Instead of showing strong NP-hardness for each of these problems separably, 
we will show one “master” reduction for the problem instead.
This reduction will then be reused to show strong NP-hardness of the problem, 
and from these two results the strong NP-hardness of all the other decision problems studied in this paper will follow.


    
	The problem with rational weights is strongly NP-complete.


	For a given instance
	A = {w_1, …, w_n} and target weight W, 
	we know that the quantities q_i, for all i = 1,…,n, have to satisfy q_i ≤ W/w_i.
	This in fact shows that the problem is in , because 
	all the quantities q_i when represented in binary can be written down in polynomial space
    and can be guessed at the beginning. 
	We can then simply verify whether ∑_i=1^n q_i · a_i = W holds
	in polynomial time by adding the rational numbers inside this sum 
	one by one (while representing all the numerators and denominators in binary).
	
	To prove strong NP-hardness, we provide a reduction from the problem for formulae (which is NP-complete due to Theorem <ref>).

	Assume we are given a formula

	
    ϕ = C_1 ∧ C_2 ∧…∧ C_m

	with m clauses C_1, …, C_m and n propositional variables x_1, …, x_n,
	where C_j = a_j ∨ b_j ∨ c_j for j = 1,…,m and
	each a_j,b_j,c_j is a literal equal to x_i or ¬ x_i
	for some i.
	For a literal l, we write that l ∈ C_j iff l is equal to a_j, b_j or c_j.
	We will now construct a set of items A of size
	polynomial in n+m and a polynomial weight W such that 
    A with the total weight W is a positive instance of iff ϕ is satisfiable.
    
	We first need to construct a list of n+m different prime numbers 
	(p_1,…,p_n+m) that are all larger than n+5.
	It suffices to pick p_i = π_i+n+5 for all i, 
	because clearly π_j > j for all j.
	Thanks to Corollary <ref>,
	we can list all these primes numbers in the unary notation
	in time and space polynomial in n+m.
	







	
	The set A will contain one item per each literal.
	We set the weight of the item corresponding to the literal x_i
	to 

	
    1 + 1p_i - 1p_i n + ∑_{j | x_i ∈ C_j }(1p_n+j - 1p_n+jm)

	and
	corresponding to the literal ¬ x_i to
	
    1 + 1p_i - 1p_in + ∑_{j |¬ x_i ∈ C_j }(1p_n+j - 1p_n+jm).


	
	Notice that each of these weights is ≥ 1 - 5/p_1 > 0,
	because each literal occurs at most four times in ϕ,
	and p_1 > 5 is the smallest prime number among p_i-s.
	At the same time, all of them are also ≤ 1 + 5/p_1 < 2.
	Moreover, they can all be written in unary using polynomial space, 
	because each literal occurs in at most four clauses and 
	so this sum will have at most 11 terms in total.
	We can then combine all these terms into a single rational number.
	Its denominator will be at most equal to p_n+m^10,
	because p_n+m is the largest prime number among p_i-s and
	the first of these terms is equal to 1.
	The numerator of this rational number has to be smaller than 2p_n+m^10,
	because we already showed this number to be < 2.
	So both of them will have size ((2n+m)^10log^10 (2n+m))
	when written down in unary, because p_n+m = π_2n+m+5 < 2 (2n+m+5)log (2n+m+5)
	due to Theorem <ref>.
	Set A has 2n such items and so all its elements' weights can be written down in unary
	using (n(2n+m)^10log^10 (2n+m)) space.
	
	Notice that the total weight of A is equal to
	
    2n + ∑_i=1^n (2p_i - 2p_i n) + ∑_j=1^m (3p_n+j - 3p_n+jm)

	because there are 2n literals, each variable corresponds to two literals, and each clause contains exactly three literals.
	As both of the two sums in this expression are telescoping, 
	we get that the total weight is in fact equal to 2n.
	We claim that the target weight W = n is achievable by picking items from A (each item possibly multiple times)
	iff ϕ is a positive instance of .
	
	(⇒) 

	Let q_i and q'_i be the number of times an item corresponding to, respectively, literal x_i and ¬ x_i is chosen
	so that the total weight of all these items is n. 
	
	For i=1,…,n, we define t_i := q_i + q_i'.
	For j=1,…,m, we define t_n+j to be the number of times an item corresponding to a literal in C_j is chosen.
	For example, if C_j = x_1 ∨¬ x_2 ∨ x_5 then t_n+j = q_1 + q'_2 + q_5.
	Finally, let T := ∑_i=1^n q_i + q'_i be the total number of items chosen.
	Notice that T ≤ W / (1 - 5/p_1) < W / (1 - 5/n+5) = n+5.
	
	Now the total weight of the selected items can be expressed using t_i-s as follows:
	
    ⋆∑_i=1^n t_i + ∑_i=1^n t_i - t_i n/p_i + ∑_j=1^m t_n+j - t_n+j m/p_n+j

	Notice that |t_i - t_i n| < n+5 and p_i > n+5 for all i=1,…,n, and
	|t_n+j - t_n+j m| < n+5 and p_n+j > n+5 for all j=1,…,m.
	It now follows from Lemma <ref> that
    (<ref>) can be equal to n if and only if
	∑_i=1^n t_i = n, and t_1=t_2=…=t_n, and t_n+1 = t_n+2 = … = t_n+m.
	The first two facts imply that for all i = 1,…,n, we have t_i = 1 and so exactly one item 
	corresponding to either x_i or ¬ x_i is chosen. 
	The last fact states that in each clause exactly the same number of items corresponding to its literals is chosen.
	It is now easy to see that the condition is satisfied by ϕ for the valuation ν such that,
    for all i ∈{1,…,n}, we set
    ν(x_i) = ⊤ iff q_i =1. 

	(⇐) 

	Let ν be a valuation for which ϕ satisfies the condition. 
	We set the quantities q_i and q'_i, the number of times an item corresponding to the literal x_i and ¬ x_i is picked, as follows.
	If ν(x_i) = ⊤ then we set q_i = 1 and q'_i = 0.
	If ν(x_i) = then we set q_i = 0 and q'_i = 1.
	
	Let us define t_i-s as before.
	Note that we now have t_i = 1 for all i = 1,…,n and 
	t_n+1 = t_n+2 = … = t_n+m, because the condition is satisfied by ν.
	We can now easily see from the expression (<ref>) that the total weight of the just picked items is equal to n.
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	


Although the strong NP-hardness complexity of the problem 
does not follow from the statement of Theorem <ref>, it follows from its proof as follows.


	The problem with rational weights is strongly NP-complete.


	Just repeat the proof of Theorem <ref> without any change. In this case we know a priori that q_i ∈{0,1}, which does not make any difference to the used reasoning. Notice that the target weight W chosen in the reduction is exactly equal to half of the total weights of all the items in A,
    so the problem instance constructed can also be considered to be a problem instance.


Now, as the problem is a generalisation of the problem, we instantly get the following result.


	The problem with rational weights is strongly NP-complete.


Finally, we observe that the 0-1 and problems are generalisations of the and problems, respectively. 
To see this just restrict the weight and profit of each item to be equal to each other as well as require V = W.
Any such instance is a positive instance of 0-1 () if and only if it is a positive instance of (respectively, ).


    The 0-1 and problems with rational weights are strongly NP-complete.




§ APPROXIMABILITY



In this section, we briefly discuss the counter-intuitive fact that 
the optimisation version of all the decision problems defined in Section <ref> admit a
fully polynomial-time approximation scheme (FPTAS) even though we just showed them to be
strongly NP-complete. First, let us restate a well-known result concerning this.

Let Π be an NP-hard optimisation problem satisfying the restrictions of Theorem 8.5 in <cit.> (first shown in <cit.>). 
If Π is strongly NP-hard, then Π does not admit an FPTAS, assuming ̸≠ .

The crucial assumption made in Theorem 8.5 of <cit.> is that the objective function is integer valued,
which does not hold in our case, so there is no contradiction.

First, let us formally define the optimisation version of some of the decision problems studied.
The optimisation version of the 0-1 problem with capacity W 
asks for a subset of items with the maximum possible total profit and whose weight does not exceed W.



As for the problem, its optimisation version asks for a subset of items whose total weight is maximal, but ≤ W.
The optimisation version of the other decision problems from Section <ref> can also be defined 
(see, e.g., <cit.>).

Now, let us formally define what we mean by an approximation algorithm for these problems.
We say that an algorithm is a constant factor approximation algorithm with a relative performance ρ
iff, for any problem instance, I, the cost of the solution that it computes, f(I), satisfies:

	
  * for a maximisation problem: (1-ρ)·(I) ≤ f(I) ≤(I)
	
  * for a minimisation problem: (I) ≤ f(I) ≤ (1+ρ)(I)

where (I) is the optimal cost for the problem instance I. 

We are particularly interested in polynomial-time approximation algorithms.
A polynomial-time approximation scheme (PTAS) is an algorithm that, for every ρ > 0,
runs in polynomial-time and has relative performance ρ.
Note that the running time of a PTAS may depend in an arbitrary way on ρ.
Therefore, one typically strives to find a fully polynomial-time approximation scheme (FPTAS), which 
is an algorithm that runs in polynomial-time in the size of the input and 1/ρ.

We will focus here on defining an FPTAS for 0-1 problem with rational coefficients.
An FPTAS for the other optimisation problems considered 
in this paper can be defined in essentially the same way
and thus their details are omitted.


	The 0-1 problem with rational coefficients admits an FPTAS.


	We claim that we can simply reuse here any FPTAS for the 0-1 problem with integer coefficients.
	Let I be a 0-1 instance with rational coefficients.
	We turn I into an instance with integer coefficients only, I',
	by the usual trick of multiplying all the rational coefficients by the least common multiple
	of the denominators of all the rational coefficients in I.
	Let us denote this least common multiple by α.    
	Assuming that all the coefficients in I are represented in binary, 
	then when multiplying them by α (again in binary representation),
	their size, as argued at the end of Section <ref>, will only increase polynomially.
	Therefore, the size of I' is just polynomially larger than I. (We should not use the unary notation because then these numbers may grow exponentially.)

	Notice that α·(I) = (I').
	In fact, the profit of any subset of items A in I', denoted by '(A), is α times bigger
	than the profit of this set of items in I, denoted by (A).
	Let us now run on I' any FPTAS for 0-1 problem with integer coefficients with relative performance ρ
	(e.g., <cit.>).
	This will return as a solution a subset of items, B, such that 
	'(B) ≥ (1-ρ) (I').
	This implies that (B) ≥ (1-ρ) (I) so the same subset of items B has also
	the same relative performance ρ on the original instance I.




§ CONCLUSIONS



In this paper we studied how the computational complexity of the , 0-1 , , 0-1 , problems 
changes when items' weights and profits can be any rational numbers.
We showed here, as opposed to the setting where all these values are integers, 
that all these problems are strongly NP-hard, which means that 
there does not exists a pseudo-polynomial algorithm for solving them unless =.
Nevertheless, we also showed that all these problem admit an FPTAS
just like in the integer setting.
Finally, we just want to point out that 
if we restrict ourselves to only 
rational weights and profits with a finite representation as decimal numerals,
then these problems are no longer strongly -complete.
This is because we could then simply multiply all the input numbers 
by a sufficiently high power of 10 and get an instance, with
all integer coefficients, whose size is polynomial in the size of the original instance.

Acknowledgements. 
We would like to thank the anonymous reviewers whose comments helped to improve this paper.
This work was partially supported by the EPSRC through grants EP/M027287/1 (Energy Efficient Control) and EP/P020909/1 (Solving Parity Games in Theory and Practice).


























plain
