
PreviousNext
In the Subset Sum problem, we are given n integers a_1,...,a_n
and a target number t, and are asked to find the subset of the
a_i's such that the sum is t. A version of the subset sum
problem is the Random Modular Subset Sum problem. In this version,
the ...
more >>>
Goerdt (1991) considered a weakened version of the Cutting Plane proof system with a restriction on the degree of falsity of intermediate inequalities. (The degree of falsity of an inequality written in the form $\sum a_ix_i+\sum b_i(1-x_i)\ge c,\ a_i,b_i\ge0$ is its constant term $c$.) He proved a superpolynomial lower bound ... more >>>
Constraint satisfaction on finite groups, with subgroups and their cosets
described by generators, has a polynomial time algorithm. For any given
group, a single additional constraint type that is not a coset of a near
subgroup makes the problem NP-complete. We consider constraint satisfaction on
groups with subgroups, near subgroups, ...
more >>>
PreviousNext