patternMinor
Proof by restriction: when is it valid to restrict to a special case?
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.
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.)
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.