Re: DAA- Reductions-how to unsubscribe from this group?
vishal makwana
On 2/3/10, shripad sarade <shripad...@gmail.com> wrote:
> *First *you have to prove a problem NP hard.
> (This can be done if you reduce known NPC problem to given problem.)
>
> *Then *you reduce given problem to known NPC problem.
> So it is NP also.
>
> Then the conclusion is given problem is NPC.
>
>
>
>
> On Thu, Feb 4, 2010 at 8:44 AM, harshjpathak <harshj...@gmail.com> wrote:
>
>>
>>
>> On Sun, Jan 31, 2010 at 8:01 PM, shripad sarade
>> <shripad...@gmail.com>wrote:
>>
>>> Given: X is NP complete
>>>
>>> if Y < X, then Y is NP class
>>> If X < Y, then Y is NP hard
>>>
>>> If Y<X and X<Y then Y is NP complete.
>>>
>>>
>>>
>>> On Sun, Jan 31, 2010 at 5:44 PM, harshjpathak
>>> <harshj...@gmail.com>wrote:
>>>
>>>>
>>>>
>>>> On Sat, Jan 30, 2010 at 10:39 PM, shripad sarade <
>>>> shripad...@gmail.com> wrote:
>>>>
>>>>> Y is NP class.
>>>>>
>>>>>
>>>>> On Sat, Jan 30, 2010 at 10:13 PM, <harshj...@gmail.com> wrote:
>>>>>
>>>>>> Suppose i have a problem X which is NP complete. Now i have another
>>>>>> problem Y whose nature i dont know. Now suppose i do a polynomial time
>>>>>> reduction of Y to X. i.e Y < X. Then what can we say about the nature
>>>>>> of problem Y?.
>>>>>>
>>>>>
>>>>>
>>>>
>>>>
>>>> okay , so if i do a reduction X<Y then i prove that Y is NP-hard, is
>>>> that
>>>> correct?. And then to prove that Y is NP complete i need to prove that Y
>>>> is
>>>> in NP so i make a reduction Y<X. Is that correct?
>>>>
>>>
>>>
>> okay i got it now. But, then how come just a reduction from hamiltonian
>> cycle to TSP proves that TSP is NP complete?. I mean what proof do we have
>> to consider that TSP is in NP?. Is it just based on the definition of NP
>> class that we can verify it in polynomial time but cant solve it, or is
>> there any other formal proof?
>>
>>
>
shripad sarade
Guidelines are given
http://groups.google.co.in/support/bin/answer.py?hl=en-uk&answer=46608