HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Proof by restriction: when is it valid to restrict to a special case?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
caserestrictionspecialvalidwhenrestrictproof

Problem

I was reading a few notes on Proof by Restriction and I am confused:

A Valid Proof by Restriction is the following:

Directed Hamiltonian Cycle Problem is NP Complete because if we look only at instances of DHC where For $G=(V,E)\quad (u,v)\in E \leftrightarrow (v,u) \in E$ then it reduces to Hamiltonian Cycle which we know is NP complete.

A wrong proof is the following:

Subset Sum problem

INSTANCE: Integers $a_1, a_2,…,a_n$ and integer B.

QUESTION: Is there a sequence of 0’s and 1’s, $x_1, x_2,…,x_n$ such that:
$$\sum_{i=1}^n a_ix_i \leq B$$

is a special case of

Real Subset Problem
INSTANCE: Integers $a_1, a_2,…,a_n$ and integer B.

QUESTION: Is there a sequence of real numbers $x_1, x_2,…,x_n$ such that:
$$\sum_{i=1}^n a_ix_i \leq B$$

so it is NP Complete.

My notes say that the this proof is wrong since it restricts the question and not the instances but I don't seem to understand the difference.

Further, I can't really understand how Proof by Restriction works; for all I know I could be restricting an NP Complete problem to a trivial case which can be solved in Polynomial time.

Solution

Think about the set of all possible instances of DHC. A subset of these instances are those where, for every directed edge $(u, v)$, there is always a matching directed edge $(v, u)$. (In general, this doesn't have to be the case, but it CAN be the case, which is why this is a valid restriction.)

Now think about the set of all possible instances of SubsetSum. For each such instance, you're supposed to answer with a set of 0/1-valued $x_i$. By your first definition, there are NO valid answers that include a real number in the $x_i$. So, when you suddenly allow real-valued solutions in the second version of SubsetSum, you're relaxing the problem, not restricting it. (You're giving yourself more leeway by allowing more possible solutions.)

Context

StackExchange Computer Science Q#7931, answer score: 3

Revisions (0)

No revisions yet.